• 把目標(biāo)值當(dāng)作背包容量，每個(gè)平方數(shù)當(dāng)作物品，題目變更為裝滿指定容量的背包，最小用幾個(gè)物品
• 會(huì)不會(huì)出現(xiàn)拼湊不出來的情況？不會(huì)，因?yàn)橛袛?shù)字1，對(duì)任意正整數(shù)百分百能拼湊出來
• 因此此題目與上一道題就變得一模一樣了

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);}
};

• 匯總