LeetCode-279.完全平方数

柔光的暖阳◎ 2024-03-25 20:21 96阅读 0赞

#### 目录 ####

*   *  题目思路
     *  回溯法
     *  动态规划
     *  动态规划(压缩)

题目来源  
[279.完全平方数][279.]

### 题目思路 ###

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

![在这里插入图片描述][80e4f40e043f41c1b5f0ed0f8c478b8f.png]

### 动态规划 ###

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为例  
![在这里插入图片描述][f238a5bd75934deb8915bd62b34a0fea.png]

![在这里插入图片描述][cb962aad975e4ad79bf1222aa9564927.png]

### 动态规划(压缩) ###

*  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状态图如下：

![在这里插入图片描述][ddac8a11243941fdb153da68634f59eb.png]  
代码实现

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];
            
        
        }
    }

![在这里插入图片描述][bb40a110500642b7858d1ea76a3f3129.png]

[279.]: https://leetcode.cn/problems/perfect-squares/
[https_donglin.blog.csdn.net_article_details_129616053]: https://donglin.blog.csdn.net/article/details/129616053
[80e4f40e043f41c1b5f0ed0f8c478b8f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4c1d5f07d9424a508c8163866945b677.png
[f238a5bd75934deb8915bd62b34a0fea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/73571c3d23244f6b874b457f04b90e57.png
[cb962aad975e4ad79bf1222aa9564927.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/fd554300a7104069b9475ba952217ccb.png
[ddac8a11243941fdb153da68634f59eb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/533bdd9e16e349a183b2482c0705ac2d.png
[bb40a110500642b7858d1ea76a3f3129.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/77bcfa60b25946c7bf86bbd8bcc8e25b.png