每日一题,今天刷到的是零钱兑换,总体思路是使用动态规划
题目描述
给你一个整数数组 coins
表示不同面额的硬币,另给一个整数 amount
表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0
。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1:
输入:amount = 5, coins = [1, 2, 5] 输出:4 解释:有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
示例 2:
输入:amount = 3, coins = [2] 输出:0 解释:只用面额 2 的硬币不能凑成总金额 3 。
问题解析
题目中给了几种硬币coins,数量不限,还给了一个总金额amount,题目要求一共有几种方案可以用这些硬币凑出总金额。
很明显这是一道需要使用动态规划来解决的问题,
我们使用一个数组dp[i]来表示当总金额为i时可以采用的方案数量。
该动态规划的边界为dp[0]=1,此时表示要求出总金额为0时的硬币选择方案,此时只有一个方案符合,即不选择任何硬币。
我们的最终目标是求出dp[amount]的值。那么我们动态规划才能求出数值呢?
对于某一个硬币来说,如果想用这枚金币求出一个大于该硬币数值的总金额,我们可以让这个总金额减去这枚硬币的面额,此时代表着当前金额再加上这每硬币的面额就可以恰好凑出总金额,这是一种方案。也就是说如果我们使用这枚硬币coin去凑出总金额amount,当仅使用一枚该硬币时,总金额可以看成现有金额currentAmount加上一枚该硬币面额,那么这种方案就时总方案数加了一,而我们的现有金额又可以使用其他金币去凑。这样我们就可以得到对于该硬币来说我们可以凑出总金额方案,并且只能用来凑大于硬币本身面额的总金额。
再具体一点,对于一个金额为x的硬币,有一个金额y大于等于该硬币面额小于等于总金额时,如果此时有一种方案的金额为y-x,那么此时在该金额的基础上加上一个金额的x的硬币,我们就凑出来了金额为y的一种方案。我们就可以对于该硬币而言,算出金额在区间在[x,amount]内的所有方案。,在这只是对于一个硬币而言,我们遍历所有的硬币,通过dp数组中的不断累加就可以得到每种金额的方案数。最后我们就可以得到总金额的方案数,这个数量由前面的累加运算得出。
这个累加的过程为无数次dp[i]+=dp[i-coin]
举个例子,我使用面额为1的硬币,我们可以使用该凑出所有大于等于一的总金额。假如现有1,2,5三个硬币,我们来凑总金额为5的方案数。
我们来看数组dp的值。
dp[0]=1
dp[1]=1,只能使用一个一元的硬币。
当计算dp[2]的时候,dp[2]初始值为0,如果使用一元硬币,可以使用两个一元硬币去凑,此时dp[2]=1,如果使用两元硬币,就可以使用一个两元硬币去凑,此时dp[2]就等于1+1等于2.此时我们就计算出了所有能凑出金额为2的方案数,记录在了dp[2]中。
当计算dp[3]的时候,其实是dp[3]经历了两次累加,第一次dp[3]=dp[3]+dp[3-1].,此时dp[2]=1,因为此时在遍历第一个一元硬币,想要得到金额2只有一种方案,因此dp[3]=1。第二次是在遍历二元硬币时,dp[3]+=dp[3-2],dp[3]加后就变成了2.此时就求出了金额为3的方案数。
依此类推,在后面的计算中,依次遍历每一枚硬币,得出使用该枚硬币时可以凑出的方案数,经过不断地遍历累加,我们就得出dp[5]的值=4.
因此最后的代码很简洁
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int i=0;i<coins.length;i++) {
for (int j = coins[i]; i <= amount; i++) {
dp[i] += dp[i - coins[i]];
}
}
return dp[amount];
}
}