題目一

給定正整數?n，找到若干個完全平方數（比如?1, 4, 9, 16, …）使得它們的和等于 n。你需要讓組成和的完全平方數的個數最少。

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

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

示例?1：

輸入：n = 12
輸出：3
解釋：12 = 4 + 4 + 4
示例 2：

輸入：n = 13
輸出：2
解釋：13 = 4 + 9

解題思路

數組定義

dp[i]代表和為 i 的完全平方數的 最少數量

轉態轉移

遍歷所有當前情況下，可以選擇的平方數

dp[i]=Math.min(dp[i-j*j]+1,dp[i]);

從和為i-j*j的情況轉移而來

代碼

class Solution {public int numSquares(int n) {int[] dp = new int[n + 1];Arrays.fill(dp,Integer.MAX_VALUE);dp[0]=0;for (int i=1;i<=n;i++){for (int j=1;j*j<=i;j++) {dp[i]=Math.min(dp[i-j*j]+1,dp[i]);}}return dp[n];}
}