算法弱鸡也能懂的动态规划刷题（一）

今天终于搞懂了一点动态规划了，给大家分享一下。
leetcode 题目为 剑指 Offer II 103. 最少的硬币数目

题目描述

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

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

题目示例

示例一：

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

示例二：

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

错误示范

有的同学可能第一直觉就是，尽量先使用较大的硬币来付，然后不够的部分再使用小的部分来补。

试试 5 + 5 + 1 = 11，哎，我们的直觉很不错嘛，这题答案就是3个硬币，一下就对了，简直so easy嘛。

哎哎哎，同学，慢点儿～

假如我们换一个示例，再用这种想法试试看，能成吗？

输入： coins = [2, 5, 7], amount = 27

试试看，用上面的直觉的的想法来看，可能是这样：

最大的面额为7元， 最多能使用 3 个面额为7元的硬币，此时的结果为 7 + 7 + 7 = 21，那么离我们的结果 27 还差6元，当我们想要使用 5元 时，还需要一个1元的硬币，但此时我们的口袋里面并没有1元的硬币，所以不能使用5元，退而求次，发现口袋里面有2元的硬币可以使用。我们把做个过程列出来

7 + 7 + 7 = 21 // 首先使用最大面额，使用了 3次
21 + 2 + 2 + 2 // 因为不能使用 5元，最后使用了 3次 2元 的硬币

我们得到的结果是 6 枚，看起来好像是正确的，但我们仔细一想，好像 7 + 5 + 5 + 5 + 5 = 27，仅需要 5枚硬币就可以，这说明直觉好像并不太好使呢，2333333🤣🤣🤣

那么到底该如何使用动态规划来解这道题呢？

第一部分：确定状态

在动态规划中，我们一般就会需要开辟一个数组，然后数组中的每个元素 代表着我们的状态。

确定状态需要有两个意识：

• 最后一步
• 子问题

最后一步

虽然我们还不知道最优的策略是什么，但最优策略肯定是K枚硬币 a₁, a₂, …, a𝚔 面值加起来是27元。

所以一定有一枚最后的硬币：a𝚔。

那么减去这枚硬币，前面的硬币的面额加起来就是 27-a𝚔

我们这里有两个关键点：

• 我们不关心前面的K-1枚硬币是怎样拼出27-a𝚔的，甚至不知道a𝚔和K是多少，但能确定前面的硬币拼出了27-a𝚔
• 因为是最优策略，所以拼出27-a𝚔的硬币数量一定要最少，否则就不是最优策略

子问题

因为是最优策略，那么子问题就是：最少用多少枚硬币拼出 27-a𝚔。
我们的原问题是最少用多少枚硬币拼出27。我们将原问题转化成了一个子问题，并且规模更小：。
那么为了简化定义，我们可以设状态

因为我们已知能使用的面额分别为 2、5、7，所以ak只能是这其中的某一个，那么就有三种情况：

• 如果ak是2，应该是(加上最后一枚硬币2)
• 如果ak是5，应该是(加上最后一枚硬币5)
• 如果ak是7，应该是(加上最后一枚硬币7)

因为要求结果是最少的硬币数，所以需要在以上三种情况中取最小值：

其中等号左边 为所需最少的硬币数。拼出所需最少的硬币数，为拼出所需最少硬币数，f(27 - 7) 为拼出所需最少硬币数，它们都加 是因为求的是，需要加上最后一枚硬币。

递归解法

这个式子一列出来，我第一个想到的就是递归算法

function f(x: number) { // f(x) = 最少用多少枚硬币拼出 x
  if (x === 0) return 0
  let res = Infinity
  if (x >= 2) { // 假设最后一枚硬币为 2
    res = Math.min(f(x - 2) + 1, res)
  }
  if (x >= 5) { // 假设最后一枚硬币为 5
    res = Math.min(f(x - 5) + 1, res)
  }
  if (x >= 7) { // 假设最后一枚硬币为 7
    res = Math.min(f(x - 7) + 1, res)
  }
  return res
}

我们来看一下这个算法的计算过程图

但是递归算法的复杂度实在是太高了，做了很多重复的计算，很明显不可取。

第二部分：转移方程

设状态 f[x] = 最少用多少枚硬币拼出x，那么对于任意 x，有方程

第三部分：初始条件和边界情况

初始条件：

对于这题的边界情况有两个问题：
x - 2，x-5，x-7 小于0怎么办？何时停下来
如不能拼出值 y，就定义 ，例如 ，使用正无穷就能表示拼不出来需要计算的值

第四部分：计算顺序

有了初始条件以及确定了边界情况，我们在解题之前，还需要确定一下计算顺序，我们这题按照从小到大的顺序去计算，也就是我们要

1. 先从初始条件开始，
2. 然后计算就是分别计算出最少用多少枚硬币拼出1—27块钱，将其放到数组中
3. 那么当我们计算到时，都已经得到结果了，不需要再次计算了

图解过程

忘记题目的同学建议再看一遍题目🤣 🤣 🤣
我们将这个解题的过程通过画图的方式来呈现出来，我们开辟一个数组，数组空间大小为amount + 1（因为从0开始要装到amount）下面的图我会把不存在的负数下标使用虚线表示。

当 x = 1 时 ，因为 1 - 2， 1 - 5， 1 - 7 全部都为负数，在数组中是找不到负数下标的，对应的全部为，那么根据我们的表达式可知，即我们手中的硬币无法拼出 1

当 x = 2 时 ，其中 2 - 5， 2 - 7 也是在数组中找不到下标的，所以对应，都为∞，而 = 1，在三个值中取得的最小值为1，也就是，即我们想要拼出 2 元最少只需要 1 枚硬币即可

后续的求解就按照上面的路数来就可以了
……我是省略号🥳 🥳 🥳
最后，我们根据这个运算方式，得出

我们可以看到，与递归算法相比，没有任何的重复计算，复杂度就降下来了，对于 27，复杂度为 27 * 3

解题

function coinChange(coins: number[], amount: number): number {
  // 开辟长度为 amount + 1 的数组用于存储状态，默认状态为正无穷（之所以是 amount + 1 是因为从 0 - amount）
  const dp = new Array(amount + 1).fill(Infinity)
  // 初始化 f[0] = 0
  dp[0] = 0

  for (let x = 1; x <= amount; x++) { // x 为不同面额，从 f[1] 开始计算到 f[amount]

    for (let j = 0; j < coins.length; j++) { // 依次从钱包里拿不同面额的硬币出来

      // 条件一：x 的面额得大于从钱包里拿出来的硬币面额，才能使用从钱包里面里面拿出来的硬币，比如你不能使用 5块 去付 4块
      // 条件二：f[x - 2] 可以通过钱包内的硬币通过组合的方式付清（这个条件判断能付清，下一个条件判断是否还有更优方式）
      // 条件三：f[x - 5] 比 f[x] 得到的值更加的小（比如此时的 f[x] 由 f[x - 2] + 1 得到）
      if (
        x >= coins[j]
        && dp[x - coins[j]] !== Infinity 
        && dp[x - coins[j]] + 1 < dp[x]
      ) {
        // 如果能付清，并且当前 f[x - 5] 的方案比 f[x - 2] 的方案更优（使用硬币数更少），则更新 f[x] 的使用最少硬币方案
         dp[x] = dp[x - coins[j]] + 1 // f[x - 5] 是子方案, + 1 是加上本次使用的硬币
      }

    }

  }
  // 根据约定 dp[x] 为 ∞ 时返回 -1，否则返回使用硬币数量
  return dp[amount] === Infinity ? -1 : dp[amount]
};

到这里，我们算是解决了这个动态规划的题目，也懂得了一点点动态规划的解题思路了，OK，本次就到这里了，动态规划后续还会继续更新，争取啃下动态规划问题！
看到这里的大帅比、大漂亮们还请点个关注，点个赞👍呗～