题目描述
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
Example1:
Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.
Example2:
Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.
dp思路
- 参考这里
- dp[0]=0
- 对所有的j,if(j*j<=i) dp[i]=min(dp[i],dp[i−j∗j]+1)
C++代码
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j * j <= i; j++){
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
};
以12为例 dp[0]=0 dp[1]=dp[0]+1=1 dp[2]=dp[1]+1=2 dp[3]=dp[2]+1=3 dp[4]=dp[0]+1=1 dp[5]=dp[4]+1=2 dp[6]=dp[5]+1=3 dp[7]=dp[6]+1=4 dp[8]=dp[4]+1=2 dp[9]=dp[0]+1=1 dp[10]=dp[9]+1=2 dp[11]=dp[10]+1=3 dp[12]=dp[8]+1=3
