一、前言
通过前一篇文章了解了动态规划是什么以后,总想找点经典的题目练练手,但是当点开一道力扣真题时,却发现一点思路也没有,本文主要是带领大家做一道经典的力扣题目
前一篇文章传送门
两道力扣真题带你入门动态规划
二、题目描述
LeetCode311. 零钱兑换
给你一个整数数组 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 = 0
输出:0
三、分析
- 这是动态规划里面典型的背包问题,硬币是物品,要将硬币凑成一定金额放入背包
- 使用dp[n]表示金额为n的零钱最少有dp[n]种组合方式
- 由于每种硬币数量无线,所以可以通过一层循环来不断使用存放硬币金额的数组
- 在组合方式没有达到最大值的时候,需要不断组合硬币来凑满金额
- 多种组合方式,选择硬币数量最少的那一种
- 返回值
四、解题思路
1️⃣初始化最大值
最大值为整型最大值 Integer.MAX_VALUE
2️⃣动态规划
1.确定dp数组及其下标含义
dp[n]表示金额为 n 的零钱最少有 dp[n] 种组合方式
2.确定递推公式
我们设定 j 为金额,i 为存放硬币的数组下标,那么 coins[i] 就代表硬币的金额,j - coins[i]代表还需要凑的金额,凑足总额为j - coins[i]的最少个数为dp[j - coins[i]],那么只需要加上一个钱币 coins[i] 即 dp[j - coins[i]] + 1。dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的
即dp[j] = min(dp[j - coins[i]] + 1, dp[j])
3.确定dp数组内元素初始值
为了防止dp数组内元素在循环中被覆盖,所以此处设为整型最大值Integer.MAX_VALUE*,而如果金额为0的话,硬币数量也为0,即dp[0] = 0
4.确定遍历
先遍历循环硬币,再遍历循环背包凑金额
5.举例推导
最终返回值应该为 dp[amount]
3️⃣输出
判断返回值是否被覆盖,如果未被覆盖就代表凑不成,返回-1,如果被覆盖就输出返回值
五、代码实现
class Solution { public int coinChange(int[] coins, int amount) { int max = Integer.MAX_VALUE; int[] dp=new int[amount+1]; for(int j = 0; j < dp.length; j++){ dp[j] = 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]; } }
六、测试代码
七、结语
本文主要是解决了一道力扣经典的动态规划题目,如果有更加简单的方法或者更加简洁的代码,欢迎留言评论