网站内容不显示百度搜索趋势
- 把目标值当作背包容量，每个平方数当作物品，题目变更为装满指定容量的背包，最小用几个物品
- 会不会出现拼凑不出来的情况？不会，因为有数字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);}
};
- 汇总