518. 零钱兑换 II

╰+攻爆jí腚メ 2022-10-09 12:19 162阅读 0赞

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

class Solution {
        public int change(int amount, int[] coins) {
            /**
            动态规划:
    
             */
    
    
             int [][ ] dp=new int[coins.length+1][amount+1];//表示前i个物品 凑成总数为 j的 情况数目
             dp[0][0]=1;
             for(int i=1;i<=coins.length;i++){
                 for(int j=0;j<=amount;j++){
                     dp[i][j]=dp[i-1][j];//当前物品不要
                     for(int  k=1;k*coins[i-1]<=j;k++){//当亲物品要, 尽量多要
                         dp[i][j]+=dp[i-1][j-k*coins[i-1]];
                     }
    
                 }
             }
             return dp[coins.length][amount];
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关 518. 零钱兑换 II ——【Leetcode每日一题】

518. 零钱兑换 II 给你一个整数数组 `coins` 表示不同面额的硬币，另给一个整数 `amount` 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。

水深无声/ 2024年03月25日 16:55/ 0 赞/ 75 阅读

相关 LeetCode-518.零钱兑换II

目录题目分析回溯法动态规划动态规划(压缩) 题目来源 [518.零钱兑换II][518._II]

╰+攻爆jí腚メ/ 2024年03月25日 16:46/ 0 赞/ 57 阅读

相关【算法挨揍日记】day44——518. 零钱兑换 II、279. 完全平方数

518. 零钱兑换 II [518. 零钱兑换 II][518. _ II] 题目描述：给你一个整数数组 `coins` 表示不同面额的硬币，另给一个整数 `a

旧城等待，/ 2024年02月05日 21:22/ 0 赞/ 50 阅读

相关【必备算法】动态规划：LeetCode题（六）322. 零钱兑换，518. 零钱兑换 II

[322. 零钱兑换²][322.] 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬

た入场券/ 2022年12月20日 01:52/ 0 赞/ 140 阅读

相关零钱兑换

零钱兑换 1、参考资料 https://leetcode-cn.com/problems/coin-change/ https://labuladong.gitb

朴灿烈づ我的快乐病毒、/ 2022年12月04日 09:58/ 0 赞/ 162 阅读

相关 518. 零钱兑换 II

> 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。 > > 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总

╰+攻爆jí腚メ/ 2022年10月09日 12:19/ 0 赞/ 163 阅读

相关 leetocde 518 零钱兑换II

前言题目：[518. 零钱兑换 II][518. _ II] 参考：[完全背包问题-大草][-]、[零钱兑换 II-力扣官方题解][II-] -----------

野性酷女/ 2022年09月16日 15:19/ 0 赞/ 142 阅读

相关 leetcode 518. Coin Change 2 | 518. 零钱兑换 II（暴力递归-＞傻缓存-＞动态规划）

题目 [https://leetcode.com/problems/coin-change-2/][https_leetcode.com_problems_coin-ch

秒速五厘米/ 2022年09月12日 03:50/ 0 赞/ 206 阅读

相关 Leetcode 518. 零钱兑换 II(DP YYDS)

题目重述给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑

àì夳堔傛蜴生んèń/ 2022年09月12日 01:54/ 0 赞/ 159 阅读

相关 518 零钱兑换 II（完全背包问题）

1. 问题描述：给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑

系统管理员/ 2022年08月30日 04:12/ 0 赞/ 250 阅读