網站內容不顯示旅游網站的網頁設計
- 把目標值當作背包容量，每個平方數當作物品，題目變更為裝滿指定容量的背包，最小用幾個物品
- 會不會出現拼湊不出來的情況？不會，因為有數字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);}
};
- 匯總