代码随想录算法训练营第三十八天-动态规划-完全背包-279.完全平方数
- 把目标值当作背包容量，每个平方数当作物品，题目变更为装满指定容量的背包，最小用几个物品
- 会不会出现拼凑不出来的情况？不会，因为有数字1，对任意正整数百分百能拼凑出来
- 因此此题目与上一道题就变得一模一样了
class Solution {
public:
int numSquares(int n) {
std::vector<int> dp(n + 1, INT_MAX);
dp.at(0) = 0;
for (int i = 1; i * i <=n; ++i) {
for (int j = i * i; j <= n; ++j) {
dp.at(j) = std::min(dp.at(j), dp.at(j - i * i) + 1);
}
}
return dp.at(n);
}
};
- 汇总