給定一個正整數n，找出最少要用幾個完全平方數(1, 4, 9, 16…）才能夠找出總和等於n的方法。例如給定n=12，則返回3，因爲12=4+4+4；給定n=13，則返回2，因爲13=4+9.
Python
當 n=13，dp[13]的答案可能是dp[12] + 1，也有可能是dp[9] + 1，也有可能是dp[4] + 1，要從上面的答案找出最小值，使用動態規劃。初始化dp[0] = 0，dp[1] = 1，dp[i] = n，遍歷2到n，不斷更新dp[i]。
以n = 13為例子, 13 – 2*2 = 9, 那麼dp[13] = min(dp[13]，dp[9] + 1), 我們要求dp[9]的最小完美平衡的個數,加上1就是dp[13]的結果。
class Solution:
def numSquares(self, n: 'int') -> 'int':
#初始化
dp = [n]*(n+1)
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
j = 1
while j*j <= i:
dp[i] = min(dp[i], dp[i-j*j] + 1)
j += 1
return dp[-1]C++
動態規劃
定義一個數組dp，其中dp[i]表示構成數字i所需的最小完全平方數數量。因此，我們需要填充整個dp數組來解決問題。初始化dp[0] = 0，因為0不需要任何完全平方數就可以得到。然後，我們將填充dp數組的其餘部分。對於i > 0，dp[i]的值可以通過考慮i – j*j（其中j*j是小於或等於i的最大平方數）並將1添加到結果來得到。
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1, INT_MAX);
dp[0] = 0; // 初始值
for (int i = 1; i <= n; i++) {
for (int j = 1; j*j <= i; j++) {
dp[i] = min(dp[i], dp[i-j*j]+1);
}
}
return dp[n];
}
};