东阳企业网站微商城建设网络工程师题库

• 把目标值当作背包容量，每个平方数当作物品，题目变更为装满指定容量的背包，最小用几个物品
• 会不会出现拼凑不出来的情况？不会，因为有数字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);}
};

• 汇总