Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

A:

----------------------------DP -----------based on the value that each iteration we can reach ---------------

class Solution {
public:
    int numSquares(int n) {
        int minRoot = int(sqrt(n));
        vector<int> squares(minRoot,0);
        for(int i = 0; i< minRoot; ++i)
            squares[i] = (1+i) *(1+i);
        
        vector<bool> B(n+1,false);
        B[0] = true;   // using 0 as the starting position 
        vector<int> seeds={0};
        int round = 1;
        for(;round<=n;++round)  // at most n rounds
        {// for each index, add a possible value
            vector<int> newSeeds;
            for(auto k : seeds)
            {
                for(auto s:squares)
                {
                    if(k+s==n)
                        return round;
                    
                    if(k+s<n && not B[k+s])
                    {
                        B[k+s] = true;
                        newSeeds.push_back(k+s);
                    }
                }
            }
            seeds = newSeeds;
        }
        return round;        
    }
};

--------------------------DP------- based on all previous values------

class Solution {
public:
    int numSquares(int n) {
        int minRoot = int(sqrt(n));
        vector<int> squares(minRoot,0);
        for(int i = 0; i< minRoot; ++i)
            squares[i] = (1+i) *(1+i);
        vector<int> res(n+1, INT_MAX);
        res[0] = 0;
        for(int i =1;i<1+n;++i)
        {
            for(auto k : squares)
            {
                int leftIndex = i - k;
                if(leftIndex>=0)
                    res[i] = 1 + min(res[i] -1 , res[leftIndex]);
            }
        }
        return res[n];
    }
};

Mistakes:

1：  加入squared number的时候，忘了update root.