Leetcode322. 零钱兑换【动态规划】

左手的ㄟ右手 2022-09-08 11:49 201阅读 0赞

难度：`中等`  
题目描述：

> 给你一个整数数组 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 { 
    public:
        int ans = 0;
        int coinChange(vector<int>& coins, int amount) { 
            if(amount<1){ 
                return 0;
            }
            // 初始化相应金额的dp数组
            vector<int> dp(amount+1, amount+1);
            dp[0]=0;
            for(int j=1;j<amount+1;j++){ 
                for(int i=0;i<coins.size();i++){ 
                    if(coins[i]<=j){ 
                        dp[j]=min(dp[j-coins[i]]+1,dp[j]);
                    }
                }
            }
            if(dp[amount]>amount){ 
                return -1;
            }else{ 
                return dp[amount];
            }
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode322.零钱兑换

//322.零钱兑换 if 0 /* 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额...

小灰灰/ 2024年04月18日 08:24/ 0 赞/ 91 阅读

相关 LeetCode-322.零钱兑换

目录题目思路回溯法动态规划动态规划(压缩) 题目来源 [322. 零钱兑换][322.] 题目思路

朱雀/ 2024年03月25日 19:39/ 0 赞/ 78 阅读

相关 leetcode322 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。示例 1

叁歲伎倆/ 2023年06月15日 12:26/ 0 赞/ 6 阅读

相关 Leetcode 322. 零钱兑换

Leetcode 322. 零钱兑换 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn.c

曾经终败给现在/ 2023年02月14日 03:06/ 0 赞/ 47 阅读

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

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

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

相关 leetcode 322. Coin Change | 322. 零钱兑换（动态规划）

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

向右看齐/ 2022年10月20日 00:55/ 0 赞/ 232 阅读

相关 LeetCode：322. 零钱兑换

链接：[https://leetcode-cn.com/problems/coin-change/][https_leetcode-cn.com_problems_coin-c

今天药忘吃喽~/ 2022年10月06日 06:55/ 0 赞/ 214 阅读

相关 Leetcode 322. 零钱兑换

题目重述给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何

秒速五厘米/ 2022年09月11日 15:18/ 0 赞/ 213 阅读

相关 Leetcode322. 零钱兑换【动态规划】

难度：`中等` 题目描述： > 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 > 计算并返回可以凑成总金额所需的最

左手的ㄟ右手/ 2022年09月08日 11:49/ 0 赞/ 202 阅读

相关 LeetCode-322. 零钱兑换

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

小咪咪/ 2022年01月27日 00:25/ 0 赞/ 242 阅读