leetcode279. Perfect Squares(basic dp)

Posted on   |   In

learn from this

  • DP

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        int numSquares(int n) {
            if(n<=0)return 0;
            int * dp = new int[n+1]();
            for(int i=1;i<=n;i++){
                dp[i]= INT_MAX;
                for(int j =1;j*j <=i;j++){
                    int tmp = dp[i-j*j]+1;
                    dp[i]=dp[i]<tmp?dp[i]:tmp;
                }
            }
            //for(int i=0;i<=n;i++)cout<< dp[i]<<' ';
            return dp[n];
        }
    };

  • BFS

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    class Solution {
    public:
        int numSquares(int n) {
            if (n <= 0)return 0;
            else if(pow((int)sqrt(n),2) == n)return 1;
            vector<int> perfectSquares;//candinates
            vector<int> cntPerfectSquares(n);//count_index
            for (int i = 1; i*i <= n; i++)
            {
                perfectSquares.push_back(i*i);
                cntPerfectSquares[i*i - 1] = 1;
                
            }
            queue<int> searchQ;
            for (auto& i : perfectSquares) searchQ.push(i);
            int currCntPerfectSquares = 1;
            while (!searchQ.empty())//BFS
            {
                currCntPerfectSquares++;
                
                int searchQSize = searchQ.size();
                for (int i = 0; i < searchQSize; i++)
                {
                    int tmp = searchQ.front();
                    for (auto& j : perfectSquares)
                    {
                        if (tmp + j == n)return currCntPerfectSquares;
                        else if ((tmp + j < n) && (cntPerfectSquares[tmp + j - 1] == 0))
                        {
                            cntPerfectSquares[tmp + j - 1] = currCntPerfectSquares;
                            searchQ.push(tmp + j);
                        }
                        else if (tmp + j > n)break;
                    }
                    searchQ.pop();
                }
            }
            return 0;
        }
    };