LeetCode题解322.coin-change

题目地址

https://leetcode.com/problems/coin-change/description/

题目描述

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.

思路

假如我们把coin逆序排列，然后逐个取，取到刚好不大于amout，依次类推。

eg: 对于 [1,2,5] 组成 11 块

- 排序[5,2,1]

- 取第一个5, 更新amout 为 11 - 5 = 6 (1⃣️)
      6 > 5 继续更新 为 6 - 5 = 1 (2⃣️)
      1 < 5 退出

- 取第二个2
      1 < 2 退出

- 取最后一个元素，也就是1

      1 === 1 更新为 1 - 1 = 0 (3⃣️)

- amout 为 0 退出


因此结果是 3

熟悉贪心算法的同学应该已经注意到了，这就是贪心算法，贪心算法更amount尽快地变得更小。
经验表明，贪心策略是正确的。注意，我说的是经验表明，贪心算法也有可能出错。就拿这道题目来说，
他也是不正确的！比如 coins = [1, 5, 11] amout = 15, 因此这种做法有时候不靠谱，我们还是采用靠谱的做法.

如果我们暴力求解，对于所有的组合都计算一遍，然后比较，那么这样的复杂度是 2 的 n 次方（这个可以通过数学公式证明，这里不想啰嗦了），
这个是不可以接受的。那么我们是否可以动态规划解决呢？答案是可以，原因就是可以划分为子问题，子问题可以推导出原问题

对于动态规划我们可以先画一个二维表，然后观察，其是否可以用一维表代替。
关于动态规划为什么要画表，我已经在这篇文章解释了

关键点解析

动态规划
子问题

用dp[i] 来表示组成i块钱，需要最少的硬币数，那么

第j个硬币我可以选择不拿这个时候，硬币数 = dp[i]
第j个硬币我可以选择拿这个时候，硬币数 = dp[i - coins[j]] + 1

和背包问题不同，硬币是可以拿任意个
对于每一个 dp[i] 我们都选择遍历一遍 coin，不断更新 dp[i]

代码

语言支持：JS，C++

JavaScript Code：

/*
 * @lc app=leetcode id=322 lang=javascript
 *
 * [322] Coin Change
 *
 * https://leetcode.com/problems/coin-change/description/
 *
 * algorithms
 * Medium (29.25%)
 * Total Accepted:    175K
 * Total Submissions: 591.9K
 * Testcase Example:  '[1,2,5]\n11'
 *
 * You are given coins of different denominations and a total amount of money
 * amount. Write a function to compute the fewest number of coins that you need
 * to make up that amount. If that amount of money cannot be made up by any
 * combination of the coins, return -1.
 *
 * Example 1:
 *
 *
 * Input: coins = [1, 2, 5], amount = 11
 * Output: 3
 * Explanation: 11 = 5 + 5 + 1
 *
 * Example 2:
 *
 *
 * Input: coins = [2], amount = 3
 * Output: -1
 *
 *
 * Note:
 * You may assume that you have an infinite number of each kind of coin.
 *
 */
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */

var coinChange = function(coins, amount) {
    if (amount === 0) {
      return 0;
    }
    const dp = Array(amount + 1).fill(Number.MAX_VALUE)
    dp[0] = 0;
    for (let i = 1; i < dp.length; i++) {
      for (let j = 0; j < coins.length; j++) {
        if (i - coins[j] >= 0) {
          dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
        }
      }
    }

    return dp[dp.length - 1] === Number.MAX_VALUE ? -1 : dp[dp.length - 1];


};

C++ Code：

C++中采用INT_MAX，因此判断时需要加上dp[a - coin] < INT_MAX以防止溢出

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        auto dp = vector<int>(amount + 1, INT_MAX);
        dp[0] = 0;
        for (auto a = 1; a <= amount; ++a) {
            for (const auto & coin : coins) {
                if (a >= coin && dp[a - coin] < INT_MAX) {
                    dp[a] = min(dp[a], dp[a-coin] + 1);
                }
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

扩展

这是一道很简单描述的题目，因此很多时候会被用到大公司的电面中。

相似问题:

518.coin-change-2

LeetCode题解计算机为什么是基于二进制的？

可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制

LeetCode题解深度优先遍历和回溯的关系？

深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。

LeetCode题解盲人买袜子。

他们都各自买了两对黑袜和两对白袜，八对袜子的布质、大小完全相同，而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢？题解：暴力破解，把袜子都拆开一人一只哈哈

LeetCode题解白石搭白塔

输入黑块和白块的数量，用输入的方块数目建塔，输出最大高度和种数，两种方法至少一层颜色不同才能算不同的方法塔满足下列要求:1. 塔底层块数和高度数值相同，逐层递减1，最高层为12. 每层颜色相同