「超详笔记」算法——动态规划（JS版）

发表于 | 更新于

判断动态规划

判断一个算法问题是否属于动态规划问题，主要依据有两点：

  • 最优子结构：一个问题的最优解是由它的各个子问题的最优解决定的。
  • 重叠子问题：解决一个问题需要拆解许多子问题，而这个子问题有重复。

最长子序列问题

LeetCode 第 300 题：给定一个无序的整数数组，找到其中最长子序列长度。

说明：可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2)。
注意：子序列和子数组不同，它并不要求元素是连续的。

示例

输入：[ 10, 9, 2, 5, 3, 7, 101, 18 ]
输出：4
即，最长的上升子序列是 [2, 3, 7, 101]，它的长度是 4。

最长子序列问题解题思路

在给定的数组里，有很多的上升子序列，例如：[10, 101]，[9, 101]，[2, 5, 7, 101]，以及 [2, 3, 7, 101]，只需要找出其中一个最长的。

思路 1：暴力法

找出所有的子序列，然后从中返回一个最长的。

从一个数组中罗列出所有的非空子数组有： n×(n + 1)/2 种，即 O(n2)，那么罗列出所有的非空子序列有 2n−1 种。复杂度将是 O(2n)。

思路 2：缩小问题规模

1、找最优子结构：输入规模对半分。

dp-1.gif

[10, 9, 2, 5] 最长的子序列应该是 [2, 5]，而 [3, 7, 101, 4] 最长的子序列是 [3, 7, 101]，由于 3 比 5 小，无法简单地组合在一起。即该方法下，总问题的解无法直观地通过子问题的最优解求得。

2、找最优子结构：每次减一个。

假设 f(n) 表示的是数组 nums[0，…，n−1] 中最长的子序列，那么 f(n−1) 就是数组 nums[0，…，n−2] 中最长的子序列，依此类推，f(1) 就是 nums[0] 的最长子序列。

假设已经解决了 f(1)，f(2)，… f(n−1) 的问题，考虑最后一个数 nums[n−1]，也必然考虑到倒数第二个数 nums[n−2]，所以 f(n) 指：如果包含了最后的数，那么最长的子序列应该是什么。注意：最后这个数必须包含在子序列当中的。

dp-2.gif

如何通过 f(1)，f(2)，…f(n−1) 推导出 f(n) 呢？由于最后一个数是 4，我们只需要在前面的 f(1)，f(2)，…f(n−1) 当中，找出一个以小于 4 的数作为结尾的最长的子序列，然后把 4 添加到最后，那么 f(n) 就一定是以 4 作为结尾的最长的子序列了。

dp-3.gif

最长的子序列并不一定会包含 4，遍历 f(1)，f(2)，…f(n−1) ，找出最长的。例如，以 101 结尾的最长的上升子序列是什么。

dp-4.gif

总结解决动态规划问题的两个难点。

（1）如何定义 f(n)。对于这道题而言，f(n) 是以 nums[n−1] 结尾的最长的上升子序列的长度。
（2）如何通过 f(1)，f(2)，…f(n−1) 推导出 f(n)，即状态转移方程。本题中，nums[n−1] 和比它小的每一个值 nums[i] 进行比较，其中 1<=i<n，加 1 即可。因此状态转移方程就是：f(n)=max (1 <= i < n−1, nums[i−1] < nums[n−1]) { f(i) } + 1。
以上证明了这个问题有一个最优的子结构。

3、找重叠子问题

在分析最后一个数 4 的时候，以 3 结尾的最长的上升子序列长度就是 f(5)，因为 3 是第 5 个数。把问题规模缩小 2 个，当前的数变成 101 的时候，找比它小的数，又发现了 3，这个时候又会去重复计算一遍 f(5)，说明该题有重叠的子问题。

因此，可以运用动态规划的方法来解决这个问题。

最长子序列问题递归+自顶而下的实现方式

用递归的方法求解状态转移方程式 f(n)=max (1 <= i < n−1, nums[i−1] < nums[n−1]) { f(i) } + 1。

  • 对于每个 n，要从 0 开始遍历
  • 在 n 之前，找出比 nums[n−1] 小的数
  • 递归地调用 f 函数，找出最大的，最后加上 1
  • 当 i 等于 0 的时候，应该返回 0；当 i 等于 1 的时候应该返回 1。

由于递归的解法需要耗费非常多的重复计算，而且很多计算都是重叠的，避免重叠计算的一种办法就是记忆化。
记忆化，就是将已经计算出来的结果保存起来，那么下次遇到相同的输入时，直接返回保存好的结果，能够有效节省了大量的计算时间。

最长子序列问题代码实现

在递归实现的基础上实现记忆化。

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
// 寻找最长子序列
// 递归，自顶而下的方式
class LongestSubsequence {
  constructor(nums) {
    this.max = 1
    this.smap = new Map()
    this.recursion(nums, nums.length)
  }
  recursion(nums, n) {
    if (this.smap.has(n)) {
      return this.smap.get(n)
    }
    if (n <= 1) {
      return n
    }

    let result = 0
    let maxEndingHere = 1

    // 从头遍历数组，递归求出以每个点为结尾的子数组中最长上升序列的长度
    for (let i = 1; i < n; i++) {
      result = this.recursion(nums, i)

      if (nums[i - 1] < nums[n - 1] && result + 1 > maxEndingHere) {
        maxEndingHere = result + 1
      }
    }

    // 判断一下，如果那个数比目前最后一个数小，那么就能构成一个新的上升子序列
    if (this.max < maxEndingHere) {
      this.max = maxEndingHere
    }

    this.smap.set(n, maxEndingHere)
    // 返回以当前数结尾的上升子序列的最长长度
    return maxEndingHere
  }
}

const arr = [10, 9, 2, 5, 3, 7, 101, 18]
const ls = new LongestSubsequence(arr)
console.log('ls: ', ls.max)

最长子序列问题递归+自顶而下的实现时间复杂度

分析递归+记忆化的时间复杂度，如下。

dp-1.gif

  • 函数 f 按序传递 n，n−1，n−2 … 最后是 1，把结果缓存并返回；
  • 递归返回到输入 n；
  • 缓存里已经保存了 n−1 个结果；
  • for 循环调用递归函数 n−1 次，从 cache 里直接返回结果。

上述过程的时间复杂度是 O(1)。即将问题的规模大小从 n 逐渐减小到 1 的时候，通过将各个结果保存起来，可以将 T(1)，T(2)，….T(n−1) 的复杂度降低到线性的复杂度。

现在，回到 T(n)，在 for 循环里，尝试着从 T(1)，T(2)….T(n−1) 里取出最大值，因此 O(T(n))=O(T(1) + T(2) + … + T(n−1))=O(1 + 2 + …. + n−1)=O(n×(n−1)/2)=O(n2)。

最后加上构建缓存 cache 的时间，整体的时间复杂度就是 O(f(n))=O(n) + O(n^2)=O(n2)。
通过记忆化的操作，我们把时间复杂度从 O(2n) 降低到了 O(n2)。
这种将问题规模不断减少的做法，被称为自顶向下的方法。但是，由于有了递归的存在，程序运行时对堆栈的消耗以及处理是很慢的，在实际工作中并不推荐。更好的办法是自底向上。

最长子序列问题自底向上的实现方式

自底向上指，通过状态转移方程，从最小的问题规模入手，不断地增加问题规模，直到所要求的问题规模为止。依然使用记忆化避免重复的计算，不需要递归。

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
class LongestSubsequence {
  constructor(nums) {
    this.max = 1
    // 初始化 dp 数组里的每个元素的值为 1，即以每个元素作为结尾的最长子序列的长度初始化为 1
    this.dp = new Array(nums.length).fill(1)
    this.init(nums)
  }

  init(nums) {
    let n = nums.length
    const { dp } = this
    // 自底而上求解每个子问题的最优解
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < i; j++) {
        if (nums[j] < nums[i] && dp[i] < dp[j] + 1) {
          dp[i] = dp[j] + 1
        }
      }
      // 当前计算好的长度与全局的最大值进行比较
      this.max = Math.max(this.max, dp[i])
    }
  }
}

const arr = [10, 9, 2, 5, 3, 7, 101, 18]
const ls = new LongestSubsequence(arr)
console.log('ls: ', ls.max)

最长子序列问题自底向上的实现方式时间复杂度

由上可知，这一个双重循环。当 i=0 的时候，内循环执行 0 次；当 i=1 的时候，内循环执行 1 次……以此类推，当 i=n−1 的时候，内循环执行了 n−1 次，因此，总体的时间复杂度是 O(1 + 2 + .. + n−1)=O(n×(n−1) / 2)=O(n2)。

线性规划

线性，就是说各个子问题的规模以线性的方式分布，并且子问题的最佳状态或结果可以存储在一维线性的数据结构里，例如一维数组，哈希表等。

解法中，经常会用 dp[i] 去表示第 i 个位置的结果，或者从 0 开始到第 i 个位置为止的最佳状态或结果。例如，最长上升子序列。dp[i] 表示从数组第 0 个元素开始到第 i 个元素为止的最长的上升子序列。

求解 dp[i] 的复杂程度取决于题目的要求，但是基本上有两种形式。

求不相邻数最大和

LeetCode 第 198 题，给定一个数组，不能选择相邻的数，求如何选才能使总数最大。
解法：这道题需要运用经典的 0-1 思想，简单说就是：“选还是不选”。

假设 dp[i] 表示到第 i 个元素为止我们所能收获到的最大总数。

如果选择了第 i 个数，则不能选它的前一个数，因此，收获的最大总数就是 dp[i−2] + nums[i]。

不选，则直接考虑它的前一个数 dp[i−1]。因此，可以推导出它的递归公式 dp[i]=max(nums[i] + dp[i−2], dp[i−1])，可以看到，dp[i] 仅仅依赖于有限个 dp[j]，其中 j=i−1，i−2。

求不相邻数最大和代码实现

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
// 求不相邻数最大和
const rob = function (nums) {
  let n = nums.length

  // 处理当数组为空或者数组只有一个元素的情况
  if (n === 0) return 0
  if (n === 1) return nums[0]

  // 定义一个 dp 数组，dp[i] 表示到第 i 个元素为止我们能收获到的最大总数
  const dp = []

  // 初始化 dp[0], dp[1]
  dp[0] = nums[0]
  dp[1] = Math.max(nums[0], nums[1])

  // 对于每个 nums[i]，考虑两种情况，选还是不选，然后取最大值
  for (let i = 2; i < n; i++) {
    dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1])
  }

  return dp[n - 1]
}

const arr = [10, 9, 2, 5, 3, 7, 101, 18]
console.log('rb: ', rob(arr))

区间规划

区间规划，就是说各个子问题的规模由不同的区间来定义，一般子问题的最佳状态或结果存储在二维数组里。一般用 dp[i][j] 代表从第 i 个位置到第 j 个位置之间的最佳状态或结果。

解这类问题的时间复杂度一般为多项式时间，对于一个大小为 n 的问题，时间复杂度不会超过 n 的多项式倍数。例如，O(n)=n^k，k 是一个常数，根据题目的不同而定。

最长回文问题

LeetCode 第 516 题，在一个字符串 S 中求最长的回文子序列。例如给定字符串为 dccac，最长回文就是 ccc。

最长回文问题解法

对于回文来说，必须保证两头的字符都相同。用 dp[i][j] 表示从字符串第 i 个字符到第 j 个字符之间的最长回文，比较这段区间外的两个字符，如果发现它们相等，它们就肯定能构成新的最长回文。而最长的回文长度会保存在 dp[0][n−1] 里。因此，可以推导出如下的递推公式。当首尾的两个字符相等的时候 dp[0][n−1]=dp[1][n−2] + 2，否则，dp[0][n−1]=max(dp[1][n−1], dp[0][n−2])。

最长回文问题代码实现

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
const LPS = function (s) {
  let n = s.length
  // 定义 dp 矩阵， dp[i][j] 表示从字符串第 i 个字符
  // 到第 j 个字符之间的最大回文
  const dp = new Array(n)

  // 初始化 dp 矩阵，将对角线元素设为 1，即单个字符的回文长度为 1
  for (let i = 0; i < n; i++) {
    dp[i] = [...new Array(n)]
    dp[i][i] = 1
  }
  console.log('dp: ', dp)
  // 从长度为 2 开始，尝试将区间扩大，一直扩大到 n
  for (let len = 2; len <= n; len++) {
    // 扩大的过程中，每次都得出区间的真实位置 i 和结束位置j
    for (let i = 0; i < n - len + 1; i++) {
      let j = i + len - 1

      // 比较一下区间首尾的字符是否相等，如果相等，就加2
      // 如果不等，从规模更小的字符串中得出最长的回文长度
      if (s.charAt(i) === s.charAt(j)) {
        dp[i][j] = 2 + (len === 2 ? 0 : dp[i + 1][j - 1])
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
      }
    }
    return dp[0][n - 1]
  }
}

console.log(LPS('abcbc'))
相关文章