279. 完全平方数

Problem: 279. 完全平方数

Code

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int numSquares(int n) {
// dp[j]表示第j等于完全完全平方数的最少数量
vector<int> dp(n+1,INT_MAX);
// dp[0] = 0
dp[0] = 0;
// 组合问题 顺序无所谓
// 完全背包 顺序
for(int j=0;j<=n;j++){
// 物品是完全平方数
for(int i=1;i*i<=j;i++){
dp[j] = min(dp[j-i*i]+1,dp[j]);
}
}
return dp[n];
}
};