​LeetCode刷题实战518:零钱兑换 II

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 零钱兑换 II,我们先来看题面:
https://leetcode-cn.com/problems/coin-change-2/

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.


Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.


You may assume that you have an infinite number of each kind of coin.


The answer is guaranteed to fit into a signed 32-bit integer.

给你一个整数数组 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 。

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


解题

https://blog.csdn.net/qq_29051413/article/details/108648948

本题有两个状态:硬币数组、金额
  设 dp[i][j] 表示前 i 个硬币中组成金额 j 的组合数。(前 i 个硬币即 coins[0]、…、coins[i-1])
  在计算 dp[i][j] 时有两个选择:
  1、一定不包含第 i-1 个硬币,此时 dp[i][j] = dp[i-1][j],即让前 i-1 的硬币去组成金额 j;
  2、一定包含第 i-1 个硬币,此时 dp[i][j] = dp[i][j-coins[i-1]],即已经包含了第 i-1 个硬币,此时金额剩下 j-coins[i-1] ,假设每个面额的硬币可以选择无数个,因此变成从前 i 个硬币中组成金额 j-coins[i-1] 的组合数。
  当 j-coins[i-1] < 0 ,说明第 i-1 个硬币面额都比金额 j 还大,只能不包含它,选择 1;
  当 j-coins[i-1] ≥ 0,说明第 i-1 个硬币可以包含和不包含,选择 1+2;
  从上面的分析中可以知道,dp 始终和 dp[i][…] 和 dp[i-1][…] 有关,因此我们可以压缩一下状态。
  设 dp[j] 表示对于硬币组成金额 j 的组合数。
  虽然状态变成了一个,但是还是得有两层 for 循环遍历,外层是前 i 个硬币,内层是金额。
  此时的选择虽然也是两个:包不包含第 i-1 个硬币,但是我们的状态只和金额有关,因此,只要不涉及金额的变化,dp[j] 就是原值。
  当 j-coins[i-1] ≥ 0 时,说明第 i-1 个硬币属于可选可不选,dp[j] = dp[j] + dp[j-coins[i-1]],第一个加数为不包含,第二个加数为包含。

class Solution {
    public int change(int amount, int[] coins) {
        int len = coins.length; // int n = coins.length;
        int[][] dp = new int[len + 1][amount + 1];
        // base_case
        for (int i = 0; i <= len; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j - coins[i - 1] < 0) { // 第 i-1 个硬币面额都比 j 大,无法包含
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                }
            }
        }
        return dp[len][amount];
    }
}


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-500题汇总,希望对你有点帮助!
LeetCode刷题实战501:二叉搜索树中的众数
LeetCode刷题实战502:IPO
LeetCode刷题实战503:下一个更大元素 II
LeetCode刷题实战504:七进制数
LeetCode刷题实战505:迷宫II
LeetCode刷题实战506:相对名次
LeetCode刷题实战507:完美数
LeetCode刷题实战508:出现次数最多的子树元素和
LeetCode刷题实战509:斐波那契数
LeetCode刷题实战510:二叉搜索树中的中序后继 II
LeetCode刷题实战511:游戏玩法分析 I
LeetCode刷题实战512:游戏玩法分析 II
LeetCode刷题实战513:找树左下角的值
LeetCode刷题实战514:自由之路
LeetCode刷题实战515:在每个树行中找最大值
LeetCode刷题实战516:最长回文子序列

​LeetCode刷题实战518:零钱兑换 II

本篇文章来源于微信公众号:程序IT圈

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/19196.html

发表评论

登录后才能评论

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息