---

題目

• 原題連接：279. 完全平方數(shù)

---

1- 思路

思路

• 動規(guī)五部曲

---

2- 實(shí)現(xiàn)

?完全平方數(shù)——題解思路

class Solution {public int numSquares(int n) {// 1. 定義 dpint[] dp = new int[n+1];//2. 遞推公式// dp[j] = Math.min(dp[j],dp[j-i*i]+1);//3. 初始化int max = Integer.MAX_VALUE;for(int i = 0 ; i < dp.length;i++){dp[i] = max;}dp[0] = 0;for(int i = 1 ; i*i <= n;i++){for(int j = i*i ; j<=n ; j++){dp[j] = Math.min(dp[j],dp[j-i*i]+1);}}return dp[n];}
}

---

3- ACM 實(shí)現(xiàn)

public class squareNum {public static int numSquares(int n){int[] dp = new int[n+1];// 2. 遞推公式// dp[j] = Math.min(j-i*i+1,dp[j]);// 3.初始化int MAX = Integer.MAX_VALUE;for (int i = 0 ; i <= n;i++){dp[i] = MAX;}dp[0] = 0;//4. 先遍歷 物品 后遍歷背包for(int i = 1; i*i <= n;i++){for(int j = i*i ; j <= n;j++){dp[j] = Math.min(dp[j - i * i] + 1, dp[j]);}}return dp[n];}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("輸入要求的完全平方數(shù)和");int n = sc.nextInt();System.out.println("結(jié)果是"+numSquares(n));}
}

---