目录

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

题目来源
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 必定大于10int 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];}
}