題目描述

給你一個整數 n ，返回 和為 n 的完全平方數的最少數量 。

完全平方數是一個整數，其值等于另一個整數的平方；換句話說，其值等于一個整數自乘的積。例如，1、4、9 和 16 都是完全平方數，而 3 和 11 不是。

題目描述

本題使用動態規劃思想來解決：

1. 狀態表達式：dp[i] 表示最少需要多少個數的平方來表示整數i;

2. 由于這些數必然落在區間[1,n的平方根]，我們來枚舉這些數，假設當前枚舉到j，那么我們還需要取若干數的平方，構成 i ? j*j，即子問題和原問題類似，動態規劃的要求，得到狀態轉移方程：

   • dp[i] = min(dp[i], dp[i - j * j] + 1)，i 表示當前數字，j * j 表示平方數

3. 將dp數組元素初始化為INT_MAX,而dp[0]單獨賦值為0為邊界條件，是為了保證狀態轉移過程中遇到 j 恰為i的平方根的情況合法。

Code

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