题目
- 原题连接:279. 完全平方数
1- 思路
思路
- 动规五部曲
2- 实现
⭐完全平方数——题解思路
class Solution {
public int numSquares(int n) {
// 1. 定义 dp
int[] 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));
}
}