LeetCode 279 完全平方数
🟡 中等
https://leetcode.cn/problems/perfect-squares/description/
注意到 1 <= n <= 10^4，这就类似于换银币[11-518零钱兑换](LeetCode 518 零钱兑换 II.md) ，只不过这里的硬币是一系列的平方数。
class Solution {
public:
int sel_not(int i, int cap) {
if (i == 0) {
if (cap == 0)
return 0;
return INT_MAX;
}
int ii = i * i;
int not_sel = sel_not(i - 1, cap);
if (cap >= ii) {
int sel = sel_not(i, cap - ii);
int left = sel == INT_MAX ? INT_MAX : 1 + sel;
return min(left, not_sel);
} else {
return not_sel;
}
}
int numSquares(int n) {
int dp[n + 1];
fill(dp, dp + n + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= 100; i++) {
for (int j = i * i; j <= n; j++) {
int sel = dp[j - i*i];
int left = sel == INT_MAX ? INT_MAX : 1 + sel;
dp[j] = min(left, dp[j]);
}
}
// return sel_not(100, n);
return dp[n];
}
};