理解动态规划

2022-04-10 09:45:30 浏览数 (1)

前言

动态规划是一种比较难以理解的算法思想，本文结合自己的理解采用通俗易懂的方式来讲解下动态规划，欢迎各位感兴趣的开发者阅读本文。

思路分析

接下来，我们通过一个例子来逐步分析，引出动态规划思想。

假设，你家里三种面值的钞票（1元、5元、11元）无数张，现在需要用这些钞票凑出某个金额出来，我们需要怎样搭配才能用最少的钞票数量凑出这个金额出来？

例如：我们要凑15元出来。

贪心思想 - 只顾眼前

依据我们的生活经验，肯定是先用面纸较大的钞票，用总金额做减法运算，思路如下：

  • 先拿1张11元的钞票，接下来我们要凑的金额就是4元（15 - 11）
  • 要凑4元出来，我们只能用1元钞票来凑，我们需要4张1元纸币（4 - 1 - 1 - 1 - 1）

15元凑出来了，我们总共用了5张钞票（1张11元的，4张1元的）。这种策略，我们称之为贪心，我们把要凑的金额设为w，需要用的钞票面额设为m，贪心策略会尽快的让w变的更小，每减少一次，我们接下来要面对的局面就是凑出w - m。

经过我们大脑计算后，这种策略凑出15元所用的钞票数量并不是最少的，我们直接使用3张5元的钞票就可以凑这个金额。

更好的方案 - 动态规划

我们使用贪心思想来解决这个问题时，只考虑了眼前的情况，格局小了，那么我们现在应该如何避免这种情况呢？

如果使用暴力枚举的方法来凑出金额，明显时间复杂度过高，太多种组合方式可以凑出这个金额了，枚举它们的时间是不可承受的。

重叠子问题

接下来，我们来尝试着，找一下这个问题的性质。

  • 一开始，如果我们取了面值为11的钞票，那么接下来面临的问题就是凑出金额为4时所需的最少钞票数量
  • 一开始，如果我们取了面值为5的钞票，那么接下来面临的问题就是凑出金额为10时所需的最少钞票数量
  • 一开始，如果我们取了面值为1的钞票，那么接下来面临的问题就是凑出金额为14时所需的最少钞票数量

经过上述分析，我们会发现这些问题都有一个共同的形式：给定一个金额，凑出这个金额所需的最少钞票数量。

我们将一个大问题拆解成了三个子问题。

接下来，我们再来分析下这三个子问题，我们用f(n)来表示凑出n所需的最少钞票数量，用cost来表示凑出w所需的钞票数量，那么：

  • 如果我们取了11，最后用掉的钞票总数就为：cost = f(4) 1
  • 如果我们取了5，最后用掉的钞票总数就为：cost = f(10) 1
  • 如果我们取了1，最后用掉的钞票总数就为：cost = f(14) 1

观察上述问题后，我们会发现一个共同点：每取一个面值的钞票，都需要计算剩余金额所需的最少钞票数，而它们的计算方法都是相同的。

这三个子问题都需要用同一种方式求解，那么它们就属于重叠子问题。

最优子结构

当我们要凑出15元的金额时，我们需要的钞票总数就为上述三种情况里所需钞票数量最少的那一个。

我们在求f(n)时，又要算出金额为n时所需的最少钞票数，例如f(10)，我们只能用2种面值的钞票（5元的和1元的）

  • 如果用5元来凑的话，我们需要的钞票数就为：f(5) 1
  • 如果用1元来凑的话，我们需要的钞票数就为：f(9) 1

我们在求f(n)时，一定会从其子问题的解决方案中找出所需硬币数量最少的那个，即：

f(n) = min(f(n - 1), f(n -5 ), f(n - 11)) 1

大问题的最优解可以由子问题的最优解推出，这个性质就称为最优子结构。

无后效性

通过上面的分析，我们知道了金额为15时，需要求出3个重叠子问题的解，选出最优的那个就是最终问题的解。

那三个子问题又有自己的重叠子问题，我们在求解这些重叠子问题时，只需要知道最终答案，不用去关心他们是如何算出来的，因为他们的计算过程并不会对之后的问题产生影响。

例如：f(4), f(10), f(14) ，我们只需要求出他们的具体值，他们的计算过程对我们之后要求解的问题没有影响。

如果给定某一阶段的状态，这一阶段以后过程的发展，不受这阶段以前各段状态的影响，就称为无后效性，即：未来与过去无关。

剪绳子

有一根长度为n的绳子，把绳子剪成m段(m、n都是整数，n > 1并且m > 1)，每段绳子的长度记为k[0], k[1], ..., k[m]。 请问k[m] * k[1] * ... * k[m]可能的最大乘积是多少? 例如：当绳子长度为8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

思路分析

接下来，我们来分析这个例子，看看能否用动态规划来解决。

根据题意，我们可知下述信息：

  • 绳子的长度肯定大于1且每次至少切一刀
  • 我们用f(n)来表示长度为n的绳子所有切法的最大乘积

那么，当绳子的长度为2时，我们只有一种切法，从中间切，这条绳子会被切为长度各为1的两小段，如下图所示：

image-20210831231406808

当n=2时，f(n) = 1 * 1 = 1，即：f(2) = 1

我们继续分析n=3的情况，如下图所示，它有2种切法

  • 切成长度为1和长度为2的两小段
  • 切成长度分别为1、1、1的三小段

image-20210901220333394

从切法2中，我们可以看出它其实就是对长度为2的绳子进行了一次切分，经过前面的分析，我们已经知道了它的所有切法的最大乘积是1，那么他们的乘积就是1 * 1 * 1 = 1。

因此， 我们不对他进行划分，直接取切法1的乘积，即: f(3) = 2

我们再来看下n=4的情况，如下图所示，它有3种切法

  • 切成长度为1和长度为3的两小段
  • 切成长度为2和长度为2的两小段
  • 切长度为别为1的四小段

image-20210901230828179

从切法1中，我们可以看出长度为3的那一段绳子的最大乘积我们已经算出来了（f(3) = 2），如果我们对这段绳子进行切分的话，乘积就变小了，所以我们选择不切分这部分绳子，那么切法1的最大乘积就为1 * 3 = 3。

从切法2中，我们可以看出那两段绳子的长度都为2，而长度为2的绳子的最大乘积我们也已经算出来了（f(2) = 1），如果切分的话，乘积就变小了，那么切法2的最大乘积就为2 * 2 = 4。

综上所述，我们可以发现这样一条规律：

  • 无论绳子最终被切成多少段，它肯定是一刀一刀来切分的
  • 绳子长度为2或者3时，不会再进行切分了，直接取其长度

那么，对于一条绳子来说，它一旦被切了一刀，就会被划分为2个子问题：

  • 切割点左侧的绳子怎么切
  • 切割点右侧的绳子怎么切

因为我们是从1开始往后推的，前面的绳子怎么切，我们已经存起来了。

分析到这里，我们发现它已经满足动态规划的2个特性了：

  • 重叠子问题：绳子被切开后，每一部分的绳子还可能再继续进行切分，每次切分要面临的子问题都是一样的
  • 最优子结构：对每部分的绳子进行切分时，我们都需要求出这部分绳子的所有切法中最大乘积是多少，满足了最优子结构这个特性

我们再来分析下n=5的情况，如下图所示，我们的第一刀有两种切法：从1位置、从2位置切，分别可以将绳子切为：

  • 长度为1和长度为4的两小段
  • 长度为2和长度为3的两小段

image-20210901235140378

我们用一个数组（result）将前面已经求出来的绳子的最大乘积（最优解）存起来，综上所述，我们知道了当绳子长度小于4时，每段绳子长度的最大乘积是固定的，即：

  • result[0] = 0
  • result[1] = 1
  • result[2] = 2
  • result[3] = 3

注意：因为绳子至少要切一刀且绳子的长度大于1，所以当绳子长度为1时是没法进行裁切的，因此它的最大乘积为1。 当绳子长度为2或3时，我们不会对它进行切分，因此他们的最大乘积就是其本身的长度。

观察上图后我们发现，当绳子长度大于等于4时，第一刀要的位置切法最多只能切到绳子长度一半的位置，每次切分出来的子问题，我们在前面已经算过并且放进了result中，我们只需将每种切法的子问题最优解相乘取出最大值即可。

当n=4时，第一刀可以切的位置可以是：1、2：

代码语言：javascript复制
result[4] = max(result[1] * result[3], result[2] * result[2])
          = max(1 * 3, 2 * 2)
        = max(3, 4)
          = 4

当n=5时，第一刀可以切的位置可以是：1、2：

代码语言：javascript复制
result[5] = max(result[1] * result[4], result[2] * result[3])
         = max(1 * 4, 2 * 3 )
          = max(4, 6)
          = 6

当n = 6时，第一刀可以切的位置可以是：1、2、3

代码语言：javascript复制
result[6] = max(result[1] * result[5], result[2] * result[4], result[3] * result[3])
     = max(1 * 6, 2 * 4, 3 * 3)
     = max(6, 8, 9)
     = 9

研究到这里，我们会发现在求子问题的最优解时，我们只关心它的结果，它的计算过程并不会影响到我们最终问题的解，那么它也满足了动态规划的最后一个性质：无后效性

递推公式

经过上面的一系列的推导，我们发现这个问题已经满足了动态规划的三个性质，那么也就是说这个问题是可以用动态规划来解决的。

经过上面的分析，我们知道了不管怎么切，绳子都会被切成两部分，然后再分别求解这两部分的最大乘积，那么当绳子长度为n时，我们就能得到如下所示的公式：

  • result[n] = result[i] * result[n - i]

n为当前要求的绳子长度，i为当前要切割位置。 绳子的不管从哪个位置切，都会被切成两段，我们求出这两段的乘积，求出每种切法的最大乘积就是长度为n的绳子的最大乘积。

实现代码

经过上面的一系列分析，我们已经彻底掌握了这道题的解法，思路有了，我们就可以用代码将其实现了，如下所示（TypeScript代码）：

代码语言：javascript复制
public cutTheRope(length: number): number {
    // 由于绳子只能整数切，所以绳子长度小于2时，无法进行裁剪
    if (length < 2) {
      return 0;
    }
    // 绳子长度为2时，只能从中间裁剪, 所有切法的最大乘积为1
    if (length === 2) {
      return 1;
    }
    // 绳子长度为3时，可以切成:
    // 1. 1 1 1
    // 2. 1 2
    // 1 * 2 > 1 * 1 * 1, 故长度为3时, 所有切法的最大乘积为2
    if (length === 3) {
      return 2;
    }

    // 创建结果数组，存储每段长度绳子切分时的最大乘积
    const products = new Array<number>(length   1);
    // 长度小于4时，绳子的最大乘积我们已经推算出来了，因此直接保存即可
    products[0] = 0;
    products[1] = 1;
    // 绳子长度为2或3时，不进行拆分，最大乘积为绳子的长度
    products[2] = 2;
    products[3] = 3;

    // 绳子长度大于4时需要对绳子进行切分，求出切分后的每段绳子的最大乘积
    for (let i = 4; i <= length; i  ) {
      // 赋初始值
      products[i] = 0;
      // 当前长度绳子的最大乘积
      let max = 0;
      // 至少切一刀，从绳子的1位置开始切，切到i/2位置。
      // 求出长度为i时，切一刀后两段绳子的最大乘积
      for (let j = 1; j <= i / 2; j  ) {
        // 根据递推公式求当前裁剪位置的两段绳子的乘积
        const product = products[j] * products[i - j];
        // 比对历史切法中两段绳子的最大乘积和当前切法两段绳子的乘积
        if (max < product) {
          // 替换最大值
          max = product;
        }
        // 修改当前绳子长度切法的最大乘积
        products[i] = max;
      }
    }
    // 每种长度绳子的最大乘积都已经求出，length位置的值就是整个问题的解
    return products[length];
}

完整代码请移步：DynamicProgramming.ts[1]

编写测试用例

我们将题目中求长度为8的绳子带入带入上述代码中，求出最大值来验证下我们的代码是否是正确的，如下所示：

代码语言：javascript复制
import DynamicProgramming from "../DynamicProgramming.ts";

const dynamicProgrammingTest = new DynamicProgramming();
const maxVal = dynamicProgrammingTest.cutTheRope(8);
console.log("最大值为", maxVal);

完整代码请移步：DynamicProgramming-test.ts[2]

运行结果如下：

image-20210906004148166

同类型例子

当你读完本文后，相信你对动态规划已经有了一定的理解，紧接着你可以尝试的做一下其他能用动态规划解决的问题，加深下理解，达到彻底掌握的目的。

我还写了其他几个动态规划问题的分析文章，如果你对此感兴趣，请移步：

  • 最少硬币找零问题[3]
  • 背包问题[4]
  • 最长公共子序列[5]
  • 矩阵链相乘[6]

写在最后

至此，文章就分享完毕了。

我是神奇的程序员，一位前端开发工程师。

参考资料

[1]DynamicProgramming.ts: https://github.com/likaia/algorithm-practice/blob/a31acfe5c9b3acbf51c9383a09003611b64ea16b/src/DynamicProgramming.ts#L9

[2]DynamicProgramming-test.ts: https://github.com/likaia/algorithm-practice/blob/7fda8ff39d15ab7a4030bd998a63e1ec331117c9/src/test-case/DynamicProgramming-test.ts

[3]最少硬币找零问题: https://juejin.cn/post/6869571836066299912#heading-7

[4]背包问题: https://juejin.cn/post/6869571836066299912#heading-10

[5]最长公共子序列: https://juejin.cn/post/6869571836066299912#heading-13

[6]矩阵链相乘: https://juejin.cn/post/6869571836066299912#heading-16

编程算法 https typescript 网络安全

0 人点赞