1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59  // @Title: 零钱兑换 (Coin Change) // @Author: 15816537946@163.com // @Date: 2019-09-22 18:05:21 // @Runtime: 12 ms // @Memory: 5.8 MB /* * @lc app=leetcode.cn id=322 lang=golang * * [322] 零钱兑换 * * https://leetcode-cn.com/problems/coin-change/description/ * * algorithms * Medium (34.89%) * Likes: 210 * Dislikes: 0 * Total Accepted: 19.6K * Total Submissions: 56.3K * Testcase Example: '[1,2,5]\n11' * * 给定不同面额的硬币 coins 和一个总金额 * amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 * * 示例 1: * * 输入: coins = [1, 2, 5], amount = 11 * 输出: 3 * 解释: 11 = 5 + 5 + 1 * * 示例 2: * * 输入: coins = [2], amount = 3 * 输出: -1 * * 说明: * 你可以认为每种硬币的数量是无限的。 * */ func coinChange(coins []int, amount int) int { dp := make([]int, amount+1) dp[0] = 0 for i := 1;i<=amount;i++ { dp[i] = amount+1 for _, c := range coins { if c <= i && dp[i] > dp[i-c] +1 { dp[i] = dp[i-c] +1 } } } if dp[amount] > amount { return -1 } return dp[amount] }