LeetCode-279.完全平方数-蒲公英云

LeetCode-279.完全平方数

题目思路

平方和的，又最小数的。
题目翻译一下：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？
这个题和零钱兑换相关，可以说简直一模一样，一定要做一下
https://donglin.blog.csdn.net/article/details/129616053

回溯法

class Solution {
    //定义一个最大值，因为题目要求求最少数量
    int ans = Integer.MAX_VALUE;
    //计数 求完全平方数数量
    int count = 0;
    public int numSquares(int n) {
        //小于0就不用求了
        if(n<=0){
            return 0;
        }
        backtracking(n,0);
        return ans;
    }
    //sum为总和
    private void backtracking(int n,int sum){
        //如果等于就求最小
        if(sum == n){
            ans = Math.min(ans,count);
        }
        //剪枝
        if(sum > n){
            return;
        }
        //求平方数  比如10  div=3   1*1+2*2+3*3 必定大于10
        int div = (int)Math.sqrt(n);
        //遍历循环
        for(int i = 1;i<=div;i++){
            sum += i*i;
            count++;
            backtracking(n,sum);
            count--;     //回溯
            sum -= i*i;  //回溯
        }
    }
}

在这里插入图片描述

动态规划

class Solution {
    public int numSquares(int n) {
        if(n<=0){
            return 0;
        }
        int div = (int)Math.sqrt(n); 
        int[][] dp = new int[div+1][n+1];
        for(int j = 0;j<=n;j++){
            dp[0][j] = Integer.MAX_VALUE;
        }
        dp[0][0] = 0;
        for(int i = 1;i<=div;i++){
            for(int j = 0;j<=n;j++){
                if(j>=i*i && dp[i][j-i*i] != Integer.MAX_VALUE){
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-i*i]+1);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[div][n];
    }
}

以n=5为例
在这里插入图片描述

在这里插入图片描述

动态规划(压缩)

1.确定dp数组（dp table）以及下标的含义

dp[j]：和为j的完全平方数的最少数量为dp[j]

2.确定递推公式

dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。

此时我们要选择最小的dp[j]，所以递推公式：dp[j] = Max.min(dp[j - i * i] + 1, dp[j]);

3.dp数组如何初始化

dp[0]表示和为0的完全平方数的最小数量，那么dp[0]一定是0。
有同学问题，那0 * 0 也算是一种啊，为啥dp[0] 就是 0呢？

看题目描述，找到若干个完全平方数（比如 1, 4, 9, 16, …），题目描述中可没说要从0开始，dp[0]=0完全是为了递推公式。

非0下标的dp[j]应该是多少呢？

从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要选最小的，所以非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。

4.确定遍历顺序

我们知道这是完全背包，
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
在动态规划：零钱兑换和本题也是一样的，是求最小数！
所以本题外层for遍历背包，内层for遍历物品，还是外层for遍历物品，内层for遍历背包，都是可以的！

5.举例推导dp数组

已输入n为5例，dp状态图如下：

在这里插入图片描述
代码实现

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