天道酬勤,学无止境

零钱兑换 II

518. 零钱兑换 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

递归 -> 记忆化搜索 -> 动态规划 -> 动态规划的优化

public class Coinsway {

    public static void main(String[] args) {
        int[] arr = {5, 10, 50, 100};
        int aim = 1000;
        System.out.println(ways(arr, aim));
        System.out.println(waysMemory(arr, aim));
        System.out.println(waysDp(arr, aim));
        System.out.println(waysDpGood(arr, aim));
    }

    public static int ways(int[] arr, int aim){
        if(arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        return process(arr, 0, aim);
    }
    /**
     *
     * @param arr 银币种类
     * @param index 当前到第几个了
     * @param rest 剩余金额
     * @return 表示有多少种方式
     * 可以自由使用arr[index...]所有的面值,每一种面值都可以使用任意张,
     * 组成rest,有多少种方法.
     */
    private static int process(int[] arr, int index, int rest) {
      /* 在for循环位置已经判断过了
       if(rest < 0){
            return 0;
        }*/
        if(index == arr.length){//没有货币可以选择了
             return rest == 0 ? 1 : 0;
        }
        int res = 0;
        for(int k = 0; k * arr[index] <= rest; k++){
            res += process(arr, index + 1, rest - k * arr[index]);
        }
        return res;
    }

/*-------------------------------------------------------------------------------------------------------------------------------------------------*/
    public static int waysMemory(int[] arr, int aim){
        if(arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        int N = arr.length;
//        HashMap<String, Integer> map = new HashMap<>();
        int[][] dp = new int[N + 1][aim + 1];

        for (int i = 0; i <= N; i++){
            for (int j = 0; j <= aim; j++) {
                dp[i][j] = -1;
            }
        }
        return processMemory(arr, 0, aim, dp);
    }

    private static int processMemory(int[] arr, int index, int rest, int[][] dp) {

        if(dp[index][rest] != -1){
            return dp[index][rest];
        }

        if(index == arr.length){//没有货币可以选择了
            dp[index][rest] = rest == 0 ? 1 : 0;
            return dp[index][rest];
        }
        int res = 0;
        for(int k = 0; k * arr[index] <= rest; k++){
            res += processMemory(arr, index + 1, rest - k * arr[index], dp);
        }
        dp[index][rest] = res;
        return dp[index][rest];
    }
/*-------------------------------------------------------------------------------------------------------------------------------------------------*/
    public static int waysDp(int[] arr, int aim){
        if(arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];

        dp[N][0] = 1;

        for(int index = N-1; index >= 0; index--){
            for(int rest = 0; rest <= aim; rest++){
    //            dp[index][rest] = ?
                int ways = 0;
                for(int k = 0; k * arr[index] <= rest; k++){
                    ways += dp[index+1][rest-(arr[index] * k)];
                }
               dp[index][rest] =  ways ;
            }
        }

        return dp[0][aim];
    }

    public static int waysDpGood(int[] arr, int aim){
        if(arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];

        dp[N][0] = 1;

        for(int index = N-1; index >= 0; index--){
            for(int rest = 0; rest <= aim; rest++){

                dp[index][rest] =  dp[index+1][rest];
                if(rest - arr[index] >= 0){
                    dp[index][rest] += dp[index][rest - arr[index]];
                }
            }
        }

        return dp[0][aim];
    }


}

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐
  • leetcode 思路——322. 零钱兑换、518. 零钱兑换 II
    leetcode 思路——322. 零钱兑换、518. 零钱兑换 II 1. 零钱兑换2. 零钱兑换 II 1. 零钱兑换 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 示例 1: 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2: 输入: coins = [2], amount = 3 输出: -1 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/coin-change 动态规划思想: 我们先定义dp,定义dp[i]为i块钱可以最少用的硬币的个数;状态变换是我们的钱变化的时候,硬币个数也在变化,所以我们可以用来算i块钱,则需要循环算i次,因为要确定他之前的需要多少个硬币数;确定状态转移方程就是,dp[i]等于它减去钱的种类的任意一种再 +1,也就是dp[i-coins[j]]+1,就比如如果是27块钱,硬币为1/2/5,那么我们就需要算27-1块钱最少需要多少硬币然后+1,27-1块钱最少需要多少硬币然后+1,27-5块钱最少需要多少硬币然后+1,最后再算他们三个的最小值即为所求; 其实就是完全背包问题 代码: class
  • 【LeetCode-518】518.零钱兑换II(动态规划)
    零钱兑换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 位符号整数 动态规划 class Solution { public int change(int amount, int[] coins) { //完全背包问题,用dp记录可以达成的目标的组合数目 //dp[i]表示价值为i的金额可被表示的目标组合数目 int[] dp = new int[amount + 1]; dp[0] = 1; for (int coin : coins) { // 记录每添加一种面额的零钱,总金额j的变化 for (int j = 1; j <= amount
  • 【LeetCode】322. 零钱兑换 & 518. 零钱兑换 II
    零钱兑换 一、题目描述 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 示例 1: 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2: 输入: coins = [2], amount = 3 输出: -1 说明: 你可以认为每种硬币的数量是无限的。 二、解题思路 & 代码 状态转移方程: class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [float('inf')] * (amount + 1) dp[0] = 0 for coin in coins: for x in range(coin, amount + 1): dp[x] = min(dp[x], dp[x - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1 复杂度分析 时间复杂度:O(Sn),其中 S 是金额,n 是面额数。我们一共需要计算 O(S) 个状态,S 为题目所给的总金额。对于每个状态,每次需要枚举 n 个面额来转移状态
  • java零钱换整程序_Java实现 LeetCode 518.零钱兑换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 位符号整数 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/coin-change-2 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 在【零钱兑换】这道题上做一些小的改变,上一题是找到凑出amount的最少硬币数目,这题是找出凑出amount的所有组合数。基础框架都是一样的,只是不再将所有的dp元素进行初始化,dp[0]=1,将上一次能够凑出的数累加即可。 class Solution { public int change(int
  • 零钱兑换II--动态规划思路解决相似问题
    本文代码采用C++ 0x01.问题 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 输入示例:5 1 2 5 输出示例:4 解释:有四种方式可以凑成总金额 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 C++函数形式为 int change(int amount, vector<int>& coins) 阅读本文之前,可以先参考:零钱兑换问题--探索动态规划的基本思想 0x02.分析问题 这是零钱兑换问题的升级版,我们来比较一下和之前的题目有什么差异,之前是求兑换到指定金额最少需要多少硬币,而这次是有多少种零钱组合可以兑换到指定的金额,一个求最小值,一个求组合数。 我们继续回想之前解决这个问题的思路,状态为dp[i]表示达到金额 i 最少需要的硬币数,状态转移方程为 DP[i]=min{DP[i],DP[i-coin]+1},思路就是金额要到 i ,我们可以假设先用掉一种零钱,然后看达到金额 i-coin 最少需要的硬币数,依次不断的迭代,把所有情况考虑完,找出里面所需硬币数最少的一个。 我们再来看这个问题,发现是不是很相似,他们的最终条件是一样的,就是一定数量的零钱兑换指定的金额,不过之前那个题中,重点考虑最少需要的硬币数,而这个题需要求出所有的组合数,事实上,在上个题的思路中
  • 【LeetCode】518. 零钱兑换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 位符号整数 方案: 参考: 1.【518. 零钱兑换 II】优化动态规划(Python3,JavaScript) 2. 背包问题9讲 解题思路 采用动态规划来做,这是一个完全背包问题。首先状态表示,状态计算 可以简化为。从二维简化为一维:。 class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [1] + [0] * amount for c in coins: for i in range(c
  • [完全背包] LeetCode 518. 零钱兑换 II
    518. 零钱兑换 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 位符号整数 解题思路(动态规划) 状态表示与转移方程:dp[j]:凑成总金额为j的金币的组合方案数dp[j] += dp[j - coins[i]] 初始化 dp[0] = 1 ,非0下标的初始化为0若要得到dp[j],需要从dp[j - coins[i]]加和而来,凑足金额为j - coins[i]的方案数为dp[j - coins[i]] C++版本 class Solution { public: int change(int amount, vector<int>& coins) { vector
  • leetcode518. 零钱兑换 II
    题目:给定不同面额的硬币和一个总金额。计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 相对于377 组合总和IV只是把内外循环i和j互换了一下(377题是有顺序的,这题的组合是没有顺序的) 虽然只是把循环位置互换了一下,dp方程也不变,但是思路是不一样的,这道题是一个二维dp优化的完全背包问题。 dp[i][v]表示最多i枚硬币组成总金额v的硬币组合数。(以前总结那个背包问题的图中:i相当于行,v相当于列) 这是个二维数组,状态类型有两种,一个是硬币的状态,一个是总金额的状态。 所以类似于377题,dp[i][v]=dp[i][v-1]+dp[i][v-2]+dp[i][v-5]+... 总结可以得到,dp[i][v]=dp[i-1][v]+dp[i][v-coin], dp[i-1][v]表示第i枚硬币不选,dp[i][v-coin]表示选择第i枚硬币。 到这里就能看出来列优化把二维dp变成一维了。 注意:这个是组合问题,没有顺序 和377不一样,把target(amount)的循环放里面 public int change(int amount, int[] coins) { if
  • 518. 零钱兑换 II(动态规划)
    518. 零钱兑换 II 题目解题思路代码 题目 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 注意: 你可以假设: 0 <= amount (总金额) <= 50001 <= coin (硬币面额) <= 5000硬币种类不超过 500 种结果符合 32 位符号整数 解题思路 这是完全背包问题。 背包问题,状态两种,不多说了。需要二维数组dp数组含义也差不多。dp[i][j]:只使用前i个物品,当背包容量为j的时候,有dp[i][j]种凑法base case也很相似,dp[0][...]=0、dp[..][0]=1不使用任何硬币,无法凑出任何金额。要凑的目标金额是0,就只有“无为而治”一种办法我们需要的dp就是dp[n][amount],需要正向遍历也只有放入、不放入这两种选择,注意,放入的话状态转移方程是dp[i][j-coins[i-1]]。这是完全背包问题,所以是i 如果是0-1背包,那就是i-1我们求的是共有多少种凑法,所以应该是放入和不放入结果的和。而不是从其中选择一个。 代码 class Solution { public int change(int amount, int[] coins) { int n=coins.length; //dp[i][j]:只使用前i个物品,当背包容量为j的时候,有dp[i
  • Java实现 LeetCode 518.零钱兑换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 位符号整数 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/coin-change-2 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 在【零钱兑换】这道题上做一些小的改变,上一题是找到凑出amount的最少硬币数目,这题是找出凑出amount的所有组合数。基础框架都是一样的,只是不再将所有的dp元素进行初始化,dp[0]=1,将上一次能够凑出的数累加即可。 class Solution { public int change(int
  • LeetCode 518. 零钱兑换 II(动态规划)
    1. 题目 给定不同面额的硬币和一个总金额。 写出函数来计算可以凑成总金额的硬币组合数。 假设每一种面额的硬币有无限个。 示例 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 位符号整数 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/coin-change-2 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 2. 解题 类似题目:LeetCode 322. 零钱兑换(DP) class Solution { public: int change(int amount, vector<int>& coins) { int i, j, n = coins.size(); vector<int> dp
  • LeetCode第 518 题:零钱兑换 II(C++)
    518. 零钱兑换 II - 力扣(LeetCode) 求的是组合数,顺序无关,只与物品的个数相关(与顺序相关的我们叫排列数)。 这儿有总结:动态规划背包问题总结_zj-CSDN博客 本题是典型的完全背包问题,amount视为背包容量,coins数组视为物品组。 完全背包问题可以三维dp,二维dp,一维dp,那就一步一步来吧。 完全背包问题(物品数量不限,选多少个都可以)的通用解法需要在两层for循环里面,再加一层选择的数量的循环(选择0//1/2/3/…/k个),然后在个数里面更优者(三层for循环)。 class Solution { public: int change(int amount, vector<int>& coins) { int n = coins.size(); //dp[i][j]表示只用前i件物品,能够装满容量j的装法种数 vector<vector<int>> dp(n+1, vector<int>(amount+1, 0)); dp[0][0] = 1; for(int i = 1; i <= n; ++i){ for(int j = 0; j <= amount; ++j){ for(int k = 0; k*coins[i-1] <= j; ++k){//选择0,1,2...个 dp[i][j] += dp[i-1][j-k*coins[i-1]
  • LeetCode题解:518. 零钱兑换 II,动态规划,JavaScript,详细注释
    原题链接:518. 零钱兑换 II 解题思路: 假设输入: amount = 5, coins = [1, 2, 5],如果用长度为amount + 1的dp数组递推,需要满足如下特性: 如果用长度为amount + 1的dp数组递推。每个索引代表了递推到的金额。每个元素是硬币组合数。0位置是初始状态,设置为1,表示都从1种组合数开始递推。 我们可以将其按照硬币种类拆分递推结果: 硬币1:[1,1,1,1,1,1]硬币2:[1,0,1,0,1,0]硬币5:[1,0,0,0,0,1]硬币1、2:[1,1,2,2,3,3]硬币1、2、5:[1,1,2,2,3,4] 递推方法如下: 依次计算每个硬币面额coin的递推结果。当前金额i,是从i - coin添加了coin而来。当前新的硬币组合数dp[i],等于上一种硬币递推到i的组合数dp[i],加上i - coin的组合数dp[i - coin]而来。状态转移方程为:dp[i] = dp[i] + dp[i - coin]。 /** * @param {number} amount * @param {number[]} coins * @return {number} */ var change = function (amount, coins) { // 不断使用硬币组合,从0元一只组合到amount //
  • leetcode 518. 零钱兑换 II
    @(labuladong的算法小抄)[dp] leetcode 518. 零钱兑换 II 题目描述 解题思路 错误解法!! 由于是组合数,所以可能会出现重复,比如金额为3,可以用[1, 2]凑出,也可以用[2, 1]凑出,下面这种解法无法避免这种重复。 而完全背包的思路确保了选择硬币的顺序性,将一堆硬币放在背包面前,如1111…2222…555555…(硬币无限),然后从第一个硬币开始选择是否装入背包,先把面额1的硬币全选完,然后再对面额2的硬币选择,因此能够避免重复组合。 /* 错误解法!! */ class Solution { public int change(int amount, int[] coins) { if (amount == 0) return 1; int n = coins.length; if (n == 0) return 0; /* 定义:当目标金额为i时,共有dp[i]种硬币组合法 */ int[] dp = new int[amount + 1]; /* base case dp[0] = 1,什么都不做就是一种组合法 */ dp[0] = 1; for (int i = 1; i <= amount; i++) { /* 遍历所有选择 */ for (int coin : coins) { if (i - coin < 0) continue
  • 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。 假设每一种面额的硬币有无限个。——完全背包问题 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] + dp[i - coin]; } } return dp[amount]; } 来源:https://gaixin.blog.csdn.net/article/details/105420241
  • LeetCode 518. 零钱兑换 II
    Description 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 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 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/coin-change-2 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 Solution 回溯 class Solution: def change(self, amount: int, coins: List[int]) -> int: if amount <= 0: return 1 if not coins: return 0 self.res = 0 def backtrack(coins, track): if sum(track) > amount: return if sum(track) == amount
  • 「代码随想录」322. 零钱兑换 【动态规划】力扣详解!
    相信很多小伙伴刷题的时候面对力扣上近两千道题目,感觉无从下手,我花费半年时间整理了Github项目:leetcode刷题攻略。 里面有100多道经典算法题目刷题顺序、配有40w字的详细图解,常用算法模板总结,以及难点视频讲解,按照list一道一道刷就可以了!star支持一波吧! 322. 零钱兑换 题目链接:https://leetcode-cn.com/problems/coin-change/ 给定不同面额的硬币 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 <= 121 <= coins[i] <= 2^31 - 10 <= amount <= 10^4 思路 在动态规划
  • Leetcode刷题记录——518. 零钱兑换 II
    0722更新 class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [1] + [0 for _ in range(amount)]#储存每种面值的凑数种类 for coin in coins: #逐个考察每一种面额 #即 一开始只考察一种面额 #而后 慢慢增加面额的种类 if coin > amount: #如果是超大面额 它自己一张都超过了amount #不可能对结果产生贡献 跳过 continue #对于这个面额以上直到amount的每一种可能的总金额 i for i in range(coin,amount+1): dp[i] += dp[i-coin] #新考察coin以后 则i的数目可以认为是i-coin的数目 return dp[amount] 将coins升序排列后 二阶dp dp[i][j]的含义是 总金额i用coins[j:]中的面值来凑的话 能有几种 dp[i][j] = dp[i-coin[j]][j] + dp[i][j+1] 含义是 总金额i用coins[j:]中的面值来凑的种数 等价于 总金额i-coin[j]后用coins[j:]中的面值来凑(即拿了一张coin[j]用) + 总金额i用coins[j-1:]中的面值来凑(尝试多考虑一种面值) 其中当i
  • LeetCode 518. 零钱兑换 II(动态规划) Java
    LeetCode 暑期打卡第八周题八,经典的类完全背包问题 题目: 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 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 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/coin-change-2 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 方法:动态规划 类似完全背包的思想 class Solution { public int change(int target, int[] nums) { int n = nums.length; int f[][] = new int[n + 1][target + 1]; f[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j <=
  • LeetCode刷题--零钱兑换
    LeetCode刷题笔记25 322. 零钱兑换代码 518. 零钱兑换 II代码 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 代码 class Solution(object): def coinChange(self, coins, amount): """ :type coins: List[int] :type amount: int :rtype: int """ dp=[amount+1 for i in range