279. Perfect Squares
給你一個數字n,求出相加等於n的數字之最小數量(每個數字要是完全平方數)。
Example:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.(最小)
12 = 9 + 1 + 1 + 1
12 = ....
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
思路:
1.這題比較偏數學,可以用動態規劃解,dp[i]表示組成數字i的最小數量。
2.因為對於一個任意數字n,他都可以被表示成n個1組成,所以dp的所有元素初始
化為i(最大組成i的完全平方數數量)。
3.然後從數字0開始一個一個的填表,外層迴圈表示dp的每一格,內層迴圈表示所
有的平方數(1開始),如果滿足小於外層迴圈的值的時候就比較之前的dp[i],和取
現在的 dp[i -j*j] + 1 哪個小,不斷的更新表格。
4.返回dp[n]
Java Code: