动规训练三：Leetcode 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 = 0
输出：0
示例 4：
输入：coins = [1], amount = 1
输出：1
示例 5：
输入：coins = [1], amount = 2
输出：2
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 231 – 1
0 <= amount <= 104
原题链接：322. 零钱兑换
题解
按照我们说的动态规划三部曲来，没看过的看我之前写的文章：告别动态规划，谈谈我的一些经验
一、定义数组的含义
我们定义 dp[i] 的含义是凑成总金额为 n 所需的最少的硬币个，那么 dp[amout] 就是我们要的答案，但是也有凑不成的情况，这时我们需要返回 -1。
二、找出数组元素之间的关系式
下面我们来找 dp 之间的关系，对于每一个硬币 coins[j]，我们只有两种选择，选或者不选。
1、如果选的话，那么就有
dp[i] = dp[i-coins[j] ] + 1，不过这里还需要注意，在选的时候，还得考虑 coins[j] 是否比 i 大，如果比 i 大的话，显然是不能选的。
2、那不选呢？不选的话，那么 dp[i] = dp[i]。
所以公示如下
dp[i] = min(dp[i], dp[i – coins[j]] + 1)。
三、找出数组初始值
初始值就比较简单了，当 i = 0 时，显然有 dp[0] = 0。
不过这里需要注意的是，我们还需要给所有 dp[i] 都赋予一个初始值，否则在递推公式 dp[i] = min(dp[i], dp[i – coins[j]] + 1) 的过程中，dp[i] 有可能会被初始值覆盖，所以我们得给 dp[i] 赋上一个尽量大的初始值，可以赋值为 amout + 1。
详情看代码吧，有些细节需要在代码，才更好说明
public class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
// 这里我们还得给dp[i]赋予一个尽量大的初始值
for(int i = 0; i <= amount; i++) {
dp[i] = amount + 1;
}
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
// 计算机 dp[i] 所需要的最少硬币数量
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
评论(2)
打卡
优秀