161 - 322 零钱兑换

题目

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

示例 1:

输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3 输出: -1

说明: 你可以认为每种硬币的数量是无限的。

解答

感觉可以排序后从大到小减

https://leetcode-cn.com/problems/coin-change/solution/dong-tai-gui-hua-tao-lu-xiang-jie-by-wei-lai-bu-ke/

大佬的套路太牛批了！！

总结一下：

1. 动态规划算法是从暴力解优化而来的

2. 优化就是用空间换时间。提高效率就是少做事

3. 还可以自底向上，从一开始慢慢往后推延，就成了动态规划

动态规划

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1
    }
    dp[0] = 0
    for i := 1; i <= amount; i++ {
        for _, coin := range coins {
            if coin <= i {
                dp[i] = min(dp[i], dp[i-coin]+1)
            }
        }
    }
    if dp[amount] == amount+1 {
        return -1
    } else {
        return dp[amount]
    }
}

Runtime: 8 ms, faster than 90.91% of Go online submissions for Coin Change.

Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for Coin Change.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount+1]*(amount+1)
        dp[0] = 0
        for i in range(amount+1):
            for coin in coins:
                if coin <= i:
                    dp[i] = min(dp[i], dp[i-coin]+1)
        return -1 if dp[amount] == amount+1 else dp[amount]

Runtime: 1392 ms, faster than 53.04% of Python3 online submissions for Coin Change.

Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Coin Change.

var coinChange = function(coins, amount) {
  const dp = new Array(amount + 1)
  for (let i = 0; i < dp.length; i++) {
    dp[i] = amount + 1
  }
  dp[0] = 0
  for (let i = 0; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1)
      }
    }
  }
  return dp[amount] == amount + 1 ? -1 : dp[amount]
};

Runtime: 108 ms, faster than 49.29% of JavaScript online submissions for Coin Change.

Memory Usage: 41.2 MB, less than 9.09% of JavaScript online submissions for Coin Change.