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

题目

• 原题连接：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));
    }
}