[Leetcode] Perfect Squares, Solution

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.

[Thoughts]
一个一维的DP，比较简单。具体看code


[Code]

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