【Hot100】LeetCode—279. 完全平方数

---

题目

• 原题连接：279. 完全平方数

---

1- 思路

思路

• 动规五部曲

---

2- 实现

⭐完全平方数——题解思路

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 实现

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("输入要求的完全平方数和");int n = sc.nextInt();System.out.println("结果是"+numSquares(n));}
}

---