【leetcode刷题】T166-零钱兑换编程题

• 2019 年 10 月 5 日
• 筆記

木又连续日更第2天（2/100）

木又的第166篇leetcode解题报告

动态规划类型第11篇解题报告

leetcode第322题：零钱兑换

https://leetcode.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  说明:  你可以认为每种硬币的数量是无限的。  

【思路】

对于所有的硬币c，dp[i] = min(dp[i], dp[i-c] + 1)

【代码】

python版本

class Solution(object):      def coinChange(self, coins, amount):          """          :type coins: List[int]          :type amount: int          :rtype: int          """          dp = [sys.maxsize] * (amount+1)          dp[0] = 0          coins.sort()          for i in range(1, amount+1):              for c in coins:                  if i - c < 0:                      break                  else:                      dp[i] = min(dp[i], dp[i-c] + 1)          return dp[-1] if dp[-1] < sys.maxsize-1 else -1  

C++版本

class Solution {  public:      int coinChange(vector<int>& coins, int amount) {          vector<int> dp(amount+1, amount*10);          dp[0] = 0;          for(int i=1; i < amount+1; i++){              for(auto c: coins){                  if(i - c < 0)                      continue;                  dp[i] = min(dp[i], dp[i-c] + 1);              }          }          return dp.back() > amount ? -1 : dp.back();      }  };