X

LEETCODE 518. Coin Change 2 解题思路分析

题目大意:

零钱兑换 II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 

示例 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。

示例 3:

输入: amount = 10, coins = [10] 
输出: 1

注意:

你可以假设:

  • 0 <= amount (总金额) <= 5000
  • 1 <= coin (硬币面额) <= 5000
  • 硬币种类不超过 500 种
  • 结果符合 32 位符号整数

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=518

解题思路分析:

这是一道典型的动态规划题目,我们定义一个dp数组,dp[i]代表凑成总金额i的硬币组合数。初始dp[0]等于1,dp[amount]是最后的解。解题时,我们需要两层循环,第一层循环每种硬币,第二层,i从当前硬币的面值循环至amount,如果想计算dp[i]的值,我们需要知道 dp[i-coin] 的值,因为 i-coin 与 i 之间只相差了当前的coin,能够凑成 i-coin 的组合,再加上当前coin,就能组成i,因此: dp[i] += dp[i-coin] 。注意这里 dp[i] 是累加的,因为,对于每种coin(第一层循环)我们都能计算出一个dp[i]。

实现代码:

public int change(int amount, int[] coins) {
    int[] dp=new int[amount+1];
    dp[0]=1;
    for(int coin : coins){
        for(int i=coin;i<=amount;i++){
            dp[i]+=dp[i-coin];
        }
    }
    return dp[amount];
}

本解法执行时间为2ms。

Runtime: 2 ms, faster than 94.26% of Java online submissions for Coin Change 2.

Memory Usage: 37.2 MB, less than 30.23% of Java online submissions for Coin Change 2.

解法二:递归加记忆数组

之前的文章我们多次讲过,绝大多数的DP题目都可以使用递归加记忆数组的方式来解题,而本题就属于那一小部分无法使用递归来解题的部分。这里首先解释一下原因。理论上使用动态规划解题时,我们需要建立一个dp数组,数组的维数决定了我们需要循环的层数。而转为递归方式时,我们实际上是将循环过程变为了递归过程,另外dp数组变成了记忆数组,除此之外没有任何区别。而本题我们注意到,在使用dp解题时,我们使用到了滚动数组,dp[i]的值是不断累加的,实际上,dp数组原始的定义应该是二维,dp[i][j]代表使用j种硬币凑成总金额i的硬币组合数。 dp[amount][coins.length]是最终的答案。

对于这种降维操作,使用递归就难以实现(至少我还不会)。不过使用二维数组的情况下还是可以使用递归来解题的。本题的递归思想实际上很像dfs,我们可以将每个coin看做是一个节点,下一个节点可以是自己或者其他任何节点,dfs路线上的节点和若等于amount的话,说明我们找到了一种组合方式。dfs完所有路线,即可统计出所有组合方式。

实现代码:

Integer[][] memo; // 记忆数组
public int change(int amount, int[] coins) {
    if(amount==0&&coins.length==0) return 1;
    if(coins.length==0) return 0;
    Arrays.sort(coins); // 排序树组
    // 初始化记忆数组
    memo=new Integer[amount+1][coins.length];
    // 递归求解
    return help(amount,coins,0);
}
// amt:需要凑成的总钱数
// coins:所有硬币
// index:可以使用的硬币范围[index, end]
int help(int amt, int[] coins, int index){
    if(amt==0) return 1;
    if(memo[amt][index]!=null) return memo[amt][index];
    int res=0;
    for(int i=index;i<coins.length;i++){
        int coin=coins[i];
        if(amt-coin>=0){
            res+=help(amt-coin,coins,i);
        }else break;
    }
    memo[amt][index]=res;
    return res;
}

本解法执行时间为25ms。

Runtime: 25 ms, faster than 8.71% of Java online submissions for Coin Change 2.

Memory Usage: 47.8 MB, less than 6.98% of Java online submissions for Coin Change 2.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-518-coin-change-2-解题思路分析/
Categories: leetcode
kwantong: