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.
采用动态规划
class Solution
{
public:
int numSquares(int n)
{
vector
res[0] = 0;
res[1] = 1;
for (int i = 1; i <= n; i++)
{
for(int j =1; jj <= i; j++)
{
res[i] = min(res[i-jj]+1,res[i]);
}
}
return res[n];
}
};