279 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.
For example,
given n = 12, return 3 because 12 = 4 + 4 + 4;
given n = 13, return 2 because 13 = 4 + 9.
Solution

class Solution {
public:
    int numSquares(int n) {
        vector<int> res(n+1, -1);
        res[0] = 0;
        for ( int i = 0; i <= n; i++ ) {
            int j = 1;
            while ( i + j*j <= n ) {
                if ( res[i+j*j] == -1 ) res[i+j*j] = res[i] + 1;
                else res[i+j*j] = min(res[i+j*j], res[i] + 1);
                j += 1;
            }
        }
        return res[n];
    }
};

Notes
Similar problem: 322 Coin Change