「数据结构与算法」动态规划学习笔记:线性动态规划

「数据结构与算法」动态规划学习笔记:线性动态规划

用动态规划解决问题的过程有以下几个关键点:

  • 状态定义
  • 状态的转移
  • 初始化
  • 边界条件

状态定义
就是定义子问题,如何表示目标规模的问题和更小规模的问题。例如常见的方法:定义状态 dp[n],表示规模为 n 的问题的解,dp[n - 1] 就表示规模为 n - 1 的子问题的解。在实战中 dp[n] 的具体含义需要首先整理清楚再往下做

状态转移
就是子问题之间的关系,例如定义好状态 dp[n],此时子问题是 dp[n-1] 等,并且大规模的问题的解依赖小规模问题的解,此时需要知道怎样通过小规模问题的解推出大规模问题的解。这一步就是列状态转移方程的过程。一般的状态转移方程可以写成如下形式

dp[n] = f(dp[i]) 其中 i < n

按照状态定义状态转移的常见形式,可以对动态规划进行分类。

其中线性动态规划的主要特点是状态的推导按照问题规模 i 从小到大依次推过去的,较大规模的问题的解依赖较小规模的问题的解

这里问题规模为 i 的含义是考虑前 i 个元素 [0..i] 时问题的解。

线性动态规划简介

线性动态规划的主要特点是状态的推导是按照问题规模 i 从小到大依次推过去的,较大规模的问题的解依赖较小规模的问题的解

这里问题规模为 i 的含义是考虑前 i 个元素 [0..i] 时问题的解。

状态定义:

dp[n] := [0..n] 上问题的解

状态转移:

dp[n] = f(dp[n-1], ..., dp[0])

从以上状态定义和状态转移可以看出,大规模问题的状态只与较小规模的问题有关,而问题规模完全用一个变量 i 表示,i 的大小表示了问题规模的大小,因此从小到大推 i 直至推到 n,就得到了大规模问题的解,这就是线性动态规划的过程。

线性动态规划是动态规划中最基本的一类。问题的形式、dp 状态和方程的设计、以及与其它算法的结合上面变化很多。按照 dp 方程中各个维度的含义,可以大致总结出几个主流的问题类型:

  • 单串
  • 双串
  • 矩阵
  • 无串

单串

单串 dp[i] 线性动态规划最简单的一类问题,输入是一个串。

线性动态规划中单串 dp[i] 的问题,状态的推导方向以及推导公式如下:
2-2-1.png

依赖比 i 小的 O(1) 个子问题:dp[n] 只与常数个小规模子问题有关

状态的推导过程:

dp[i] = f(dp[i - 1], dp[i - 2], ...)

时间复杂度 O(n),空间复杂度 O(n) 可以优化为 O(1),例如 LeetCode 70, 801, 790, 746 都属于这类。
如上图所示,虽然蓝紫色部分的 dp[i-1], dp[i-2], ..., dp[0] 均已经计算过,但计算橙色的当前状态时,仅用到 dp[i-1],这属于比 i 小的 O(1) 个子问题
例如,当 f(dp[i-1], ...) = dp[i-1] + nums[i] 时,当前状态 dp[i] 仅与 dp[i-1] 有关。这个例子是一种数据结构前缀和的状态计算方式。

例题:
53.PNG

一个数组有很多个子数组,求哪个子数组的和最大。可以按照子数组的最后一个元素来分子问题,确定子问题后设计状态

dp[i] := [0..i] 中,以 nums[i] 结尾的最大子数组和

状态的推导是按照 i 从 0 到 n - 1 按顺序推的,推到 dp[i],时,dp[i - 1], ..., dp[0] 已经计算完。因为子数组是连续的,所以子问题 dp[i] 其实只与子问题 dp[i - 1] 有关。如果 [0..i-1] 上以 nums[i-1] 结尾的最大子数组和(缓存在 dp[i-1] )为非负数,则以 nums[i] 结尾的最大子数组和,就在 dp[i-1] 的基础上加上 nums[i] 就是 dp[i] 的结果否则以 i 结尾的子数组就不要 i-1 及之前的数,因为选了的话子数组的和只会更小。
因此,状态转移方程如下:

dp[i] = nums[i] + max(dp[i - 1], 0)

依赖比 i 小的 O(n) 个子问题:dp[n] 与此前的更小规模的所有子问题 dp[n - 1], dp[n - 2], ..., dp[1] 都可能有关系

状态推导过程如下:

dp[i] = f(dp[i - 1], dp[i - 2], ..., dp[0])

如上图所示,计算橙色的当前状态 dp[i] 时,蓝紫色部分为此前计算过的状态 dp[i-1], ..., dp[0] 均有可能被用到,在计算 dp[i] 时需要将它们遍历一遍完成计算。
其中 f 常见的有 max/min,可能还会对 i-1,i-2,...,0 有一些筛选条件,但推导 dp[n] 时依然是 O(n) 级的子问题数量。

双串

有两个输入从串,长度分别为 m, n,此时子问题需要用 i, j 两个变量表示,分别代表第一个串和第二个串考虑的位置 dp[i][j]:=第一串考虑[0..i],第二串考虑[0..j]时,原问题的解

较大规模的子问题只与常数个较小规模的子问题有关,其中较小规模可能是 i 更小,或者是 j 更小,也可以是 i,j 同时变小
其中一种最常见的状态转移形式:推导 dp[i][j] 时,dp[i][j] 仅与 dp[i-1][j], dp[i][j-1], dp[i-1][j-1]

线性动态规划中双串 dp[i][j] 的问题,状态的推导方向以及推导公式如下

2-2-2.png

如图所示,绿色部分的 dp[i-1 ~ 0][j-1 ~ 0] 均已经计算过,但计算橙色的当前状态时,仅用到 dp[i-1][j], dp[i][j-1], dp[i-1][j-1],即比 i, j 小的 O(1)O(1) 个子问题。

这种形式的线性 DP 的代码常见写法

for i = 1..m
    for j = 1..n
        dp[i][j] = f(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

时间复杂度 O(mn)O(mn),空间复杂度 O(mn)O(mn)

以上是 O(1)O(1) 转移的情况,即计算 dp[i][j] 时,虽然绿色部分的子问题均已经计算完,但只需要用到 dp[i-1][j], dp[i][j-1], dp[i-1][j-1]。也可能出现更高复杂度的转移,类似单串中依赖比 i 小的 O(n)O(n) 个子问题的情况。

经典问题:最长公共子序列

给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。

思路

单个数组或者字符串要用动态规划时,可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果;当两个数组或者字符串要用动态规划时,可以把动态规划定义成两维的 dp[i][j] ,其含义是在 A[0:i] B[0:j] 之间匹配得到的想要的结果。

状态定义

可以定义 dp[i][j] 表示 text1[0:i-1] text2[0:j-1] 的最长公共子序列。 (注: text1[0:i-1] 表示的是 text1 的 第 0 个元素到第 i - 1 个元素,两端都包含)
之所以 dp[i][j] 的定义不是 text1[0:i] text2[0:j] ,是为了方便当 i = 0 或者 j = 0 的时候, dp[i][j] 表示的为空字符串和另外一个字符串的匹配,这样 dp[i][j] 可以初始化为 0。

状态转移

  • text1[i - 1] == text2[j - 1] 时,说明两个子字符串的最后一位相等,所以最长公共子序列又增加了 1,所以 dp[i][j] = dp[i - 1][j - 1] + 1;举个例子,比如对于 ac 和 bc 而言,他们的最长公共子序列的长度等于 a 和 b 的最长公共子序列长度 0 + 1 = 1。
  • text1[i - 1] != text2[j - 1] 时,说明两个子字符串的最后一位不相等,那么此时的状态 dp[i][j] 应该是 dp[i - 1][j] dp[i][j - 1] 的最大值。举个例子,比如对于 ace 和 bc 而言,他们的最长公共子序列的长度等于 ① ace 和 b 的最长公共子序列长度0 与 ② ac 和 bc 的最长公共子序列长度1 的最大值,即 1。

综上状态转移方程为:

dp[i][j] =
1. dp[i-1][j-1] + 1  (text1[i] == text2[j])
2. max(dp[i][j-1], dp[i-1][j])  (text1[i] != text2[j])

状态初始化

初始化就是要看当 i = 0 与 j = 0 时, dp[i][j] 应该取值为多少。

当 i = 0 时, dp[0][j] 表示的是 text1text1 中取空字符串 跟 text2 的最长公共子序列,结果肯定为 0。
当 j = 0 时, dp[i][0] 表示的是 text2text2 中取空字符串 跟 text1 的最长公共子序列,结果肯定为 0。
综上,当 i = 0 或者 j = 0 时, dp[i][j] 初始化为 0。

经典问题:最长重复子数组

给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

思路

区分两个概念:

  • 子序列可以是不连续的
  • 子数组(子字符串)需要是连续的

状态定义

定义 dp[i][j] 为以 nums1[i - 1] nums2[j - 1] 为末尾项的公共子数组的长度。

状态转移

  • nums1[i - 1] == nums2[j - 1] 时,以 nums1[i - 1] nums2[j - 1] 为末尾项的公共子数组 dp[i][j] 的长度保底为1,要考虑它俩的前缀数组 dp[i - 1][j - 1] 能为它俩提供多大的公共长度。
  • nums1[i - 1] != nums2[j - 1] 时,以 nums1[i - 1] nums2[j - 1] 为末尾项的公共子数组 dp[i][j] 的长度为0。

综上状态转移方程为:

dp[i][j] =
1. dp[i-1][j-1] + 1  (nums1[i] == nums2[j])
2. 0  (nums1[i] != nums2[j])

经典问题:编辑距离

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符

思路

我们可以对任意一个单词进行三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

题目给定了两个单词,设为 A 和 B,这样我们就能够六种操作方法(插入A、插入B、删除A、删除B、替换A、替换B)。

但可以发现:

  • 对单词 A 删除一个字符和对单词 B 插入一个字符是等价的。例如当单词 A 为 doge,单词 B 为 dog 时,既可以删除单词 A 的最后一个字符 e,得到相同的 dog,也可以在单词 B 末尾添加一个字符 e,得到相同的 doge
  • 对单词 B 删除一个字符和对单词 A 插入一个字符也是等价的
  • 对单词 A 替换一个字符和对单词 B 替换一个字符是等价的。例如当单词 A 为 bat,单词 B 为 cat 时,修改单词 A 的第一个字母 b -> c,和修改单词 B 的第一个字母 c -> b 是等价的。

这样以来,本质不同的操作实际上只有三种:

  • 在单词 A 中插入一个字符
  • 在单词 B 中插入一个字符
  • 修改单词 A 的一个字符

状态定义

定义 dp[i][j] word1 中前 i 个字符,变换到 word2 中前 j 个字符,最短需要操作的次数。
需要考虑 word1 word2 一个字母都没有,即全增加or全删除的情况,所以预留 dp[0][j] dp[i][0]

状态转移

  • D[i][j-1] word1 的前 i 个字符和 word2 的前 j - 1 个字符编辑距离的子问题。即对于 word2 的第 j 个字符,我们在 word1 的末尾添加了一个相同的字符,那么 D[i][j] 最小可以为 D[i][j-1] + 1
  • D[i-1][j] word1 的前 i - 1 个字符和 word2 的前 j 个字符编辑距离的子问题。即对于 word1 的第 i 个字符,我们在 word2 的末尾添加了一个相同的字符,那么 D[i][j] 最小可以为 D[i-1][j] + 1
  • D[i-1][j-1] word1 i - 1 个字符和 word2 的前 j - 1 个字符编辑距离的子问题。即对于 word2 的第 j 个字符,我们修改 word1 的第 i 个字符使它们相同,那么 D[i][j] 最小可以为 D[i-1][j-1] + 1。特别地,如果 word1 的第 i 个字符和 word2 的第 j 个字符原本就相同,那么我们实际上不需要进行修改操作。在这种情况下, D[i][j] 最小可以为 D[i-1][j-1]

综上状态转移方程为:

dp[i][j] =
1. min(dp[i][j−1] + 1, dp[i−1][j] + 1, dp[i−1][j−1]) (word1[i - 1] == word2[j - 1])
2. min(dpi][j−1], dp[i−1][j], dp[i−1][j−1]) + 1 (word1[i - 1] != word2[j - 1])

总结

动态规划中最重要的三个概念:最优子结构重复子问题无后效性

  • 最优子结构:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构。
  • 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
  • 重复子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)

参考

https://leetcode-cn.com/leetb...

你可能感兴趣的