279. Perfect Squares

Example: for n = 4
1st round:
    i = 1, j = 1: dp = [1]
2nd round:
    i = 2, j = 1: dp = [1 2]
3rd round:
    i = 3, j = 1: dp = [1 2 3]
4th round:
    i = 4, j = 1: dp = [1 2 3 4]
    i = 4, j = 2: dp = [1 2 3 1]

From the example above, let dp[i] be the least number of perfect squares for number i. So, for 1 <= j <= sqrt(i), we have dp[i] = min(dp[i], dp[i-j*j]+1).

1:  class Solution {  
2:  public:  
3:    int numSquares(int n) {  
4:      vector<int> dp(n+1, INT_MAX);  
5:      dp[0] = 0;  
6:      for (int i = 1; i <= n; i++) {  
7:        for (int j = 1; j*j <= i; j++) {  
8:          dp[i] = min(dp[i], dp[i-j*j]+1);  
9:        }  
10:      }  
11:      return dp[n];  
12:    }  
13:  };