本文主要是介绍Leetcoder Day40｜ 动态规划part07，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
322. 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
- 输入：coins = [1, 2, 5], amount = 11
- 输出：3
- 解释：11 = 5 + 5 + 1
示例 2：
- 输入：coins = [2], amount = 3
- 输出：-1
示例 3：
- 输入：coins = [1], amount = 2
- 输出：2
提示：
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
本题和昨天的零钱兑换题设最大的区别在于，求所需的最少的硬币个数。则这时候dp[j]为金额总和为j时所需最少硬币个数。初始化，当金额总和为0时，所需硬币数为0。因此当满足条件时：判断dp[j]和dp[j-coins[i]]+1谁更小，输出更小的
这里需要注意的地方是⚠️：首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
其他下标对应的数值呢？考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。所以下标非0的元素都是应该是最大值。
class Solution {public int coinChange(int[] coins, int amount) {int[] dp=new int[amount+1];int max=Integer.MAX_VALUE;Arrays.fill(dp, max);dp[0]=0;for(int i=0;i<coins.length;i++){for(int j=coins[i];j<=amount;j++){if(dp[j-coins[i]]!=max){dp[j]= Math.min(dp[j], dp[j-coins[i]]+1);}}}return dp[amount]==max ? -1:dp[amount];}
}279.完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
- 输入：n = 12
- 输出：3
- 解释：12 = 4 + 4 + 4
示例 2：
- 输入：n = 13
- 输出：2
- 解释：13 = 4 + 9
提示：
- 1 <= n <= 10^4
dp含义：本题dp[j]就是和为j的最小完全平方数量
递推公式：dp[j]=dp[j-i^2]+1
初始化：当j=1 时 dp[j]=1 ，因为但凡一个整数都可以被1累加到，所以不需要判断剩下的数是否为完全平方数。这里依然需要初始化一个最大值防止被覆盖。
这里出现了错误，如果我从dp[1]=1开始初始化，会发现结果是下面这样的：
class Solution {public int numSquares(int n) {int[] dp= new int[n+1];int max=Integer.MAX_VALUE;Arrays.fill(dp, max);dp[1]=1;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];}
}
因为在这里把dp[1]也给设置为max了，而在遍历时没有判断dp[1]导致后面一直都等于max，所以应该从dp[2]开始初始化:
class Solution {public int numSquares(int n) {int[] dp= new int[n+1];int max=Integer.MAX_VALUE;for(int i=2;i<=n;i++){dp[i]=max;}//Arrays.fill(dp, max);dp[1]=1;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];}
}这篇关于Leetcoder Day40｜ 动态规划part07的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
