动态规划 – 常见普通题型及状态表示

正文索引 [隐藏]

上一节我们讲了序列型动态规划,一点精髓就是动态规划最重要的是状态间的顺序(阶段划分)。这个顺序可能是题目给你的,也可能是需要自己转化出来的,确定了这个顺序之后,就可以类比序列型动态规划做了。可以说,熟练掌握了序列型动态规划,你就在代码层面和逻辑层面掌握了动态规划,其他所有题目都可以使用自己的智慧解答出来。

那么接下来,各位同学要做的就是多做题、多接触不同类型,积累寻找阶段划分、状态表示与状态转移的经验与感觉。那么,我想把一些比较普通的类型一次性全部讲了。

坐标型 & 双序列型

序列型动态规划给你一个序列,一倍的快乐。坐标型一般给你一个 2D 数组,双序列型动态规划一般给你两个字符串 S, T(不要问我为啥这里的序列是字符串,问就是题面太难编)。

这两种题目的状态表示本质上来说是一个二维表格,两倍的快乐!那么,状态表示一般为 dp[i][j] 表示位于这个表格的第 i 行第 j 列的答案。,或者。

这样的题目,LeetCode 里面还是不少的,现列举一些上来就给你 2D 数组的:62. 不同路径63. 不同路径 II64. 最小路径和576. 出界的路径数931. 下降路径最小和1289. 下降路径最小和 II1301. 最大得分的路径数目
都是给你一个 2D 棋盘,然后你可以在上面按照某种规则走动,最后要求最值或者符合要求的方案数量。状态标识 dp[i][j] 就是坐标 (i, j) 的答案,允许走动的规则就是状态转移的规则。

LC 62. 不同路径

状态表示: dp[i][j]表示走到了第 i 行第 j 列的方案数
边界:dp[1][1] = 1
状态转移:dp[i][j] = dp[i − 1][j] + dp[i][? − j]

计算样例 3 行 7 列的方案数,动态规划的状态表格为:
LC 62 DP Table

给你两个字符串的题目,经典的也有许多:72. 编辑距离1092. 最短公共超序列1143. 最长公共子序列
都是给你两个字符串,在这两个字符串上进行匹配的操作,dp[i][j] 表示匹配完了字符串 S[1\cdots i], T[1\cdots j] 的答案,状态转移一般就对应匹配操作。

LC 1143. 最长公共子序列

状态表示: dp[i][j] 表示串 text1[1\cdots i]text2[1\cdots j] 的最长公共子序列
边界:dp[0][0]=1
状态转移:

dp[i][j]=
\begin{cases}
dp[i−1][j−1]+1, text1[i]=text2[j],\\
max⁡(dp[i−1][j],dp[i][j−1]),otherwise.
\end{cases}

使用样例字符串 ace, abcde 推出的动态规划状态表格为:
LC 1143 DP Table

划分型动态规划

划分型动态规划的特点就是给你一个序列,你要把它不重不漏的划分成 K 个区间。这种问题一个很直接的思路就是 dp[i] 表示考虑了序列前 i 个元素。

这样的题目在 LeetCode 里面也很经典:132. 分割回文串 II410. 分割数组的最大值1278. 分割回文串 III1335. 工作计划的最低难度

考虑这类问题的转移,我们通场先枚举一个状态 dp[i],然后考虑将序列 [i + 1, j] 接在后面自成一段,转移到状态 dp[j](主动转移)。想想看这里的被动转移是什么。

如果严格分成 K 段,那么应该增加一维 [k] 表示当前分成了几段。本题型重要的还是:将序列 [i + 1, j] 接在后面自成一段这种状态转移的思想。

LC 132. 分割回文串 II

状态表示: dp[i] 表示将 ?[1\cdots i] 拆分成回文串的最少拆几段。
边界:dp[0]=0
状态转移:dp[i]=\min⁡ {dp[j]+1 },j<i~and~s[j+1\cdots i]~is~palindrome

这道题目和上一讲序列型动态规划类似,那我们同样也可以列出这样一个动态规划状态转移的表:
132 DP Table

状态压缩动态规划

我们暂时只讨论比较简单的状态压缩动态规划,先不讨论基于连通性状态压缩的动态规划。

状态压缩动态规划的特点就是使用一个数的二进制形式保存状态,比如,0,1,2,3 四把椅子有没有人座,我们可以使用 [0/1][0/1][0/1][0/1] 来表示,也可以使用 [0\cdots 7] 来表示。

状态压缩示例

那么引入了二进制来表示状态之后,写代码就方便了许多。想想看,你的状态中有这么多维都需要分别写代码处理是不是很头疼呢。

这里,普及一些位运算常用写法,假设 bits 为状态压缩的数:

  • 判断第 j 位是否为 1: (bits>>j)&1
  • 将第 j 位变成 1: bits|(1<<j)
  • 将第 j 为变成 0bits&~(1<<j)

额外说一点,其实需要状态压缩的题目非常好分辨,你看数据范围的某一维度非常小,那么十有八九是留给你状态压缩用的。

这种题目,LeetCode 里并不多,最新的一期周赛中又出现:1349. 参加考试的最大学生数

LC

状态表示: dp[i][bits] 表示第 i 行座位情况为 bitsi 合法状态下最多坐多少人。(bits0 表示没人坐;1 表示有人坐)
边界:dp[0][0]= 0
状态转移:dp[i][bits_{cur}]=max(dp[i][bits_{cur}],dp[i−1][bits_{pre}]+bitcount(bits_{cur}))ibits_{cur}i-1bits_{pre} 合法:

  • i 行情况 bits_{cur},没有人坐到坏的位置上
  • i−1 行情况 bits_{pre}i 行情况 bits_{cur},没有人可以作弊
    • i 行第 j 个位置有人坐,那么 ij-1, j+1 两个位置不能做坐人
    • i 行第 j 个位置有人坐,那么 i-1j-1, j+1 两个位置不能做坐人

因为上图箭头根部的 1,所以指向的四个位置都必须是 0。

1349 状态压缩

Take Home Message

坐标型、双序列型动态规划:状态本质为二维表格,用 dp[i][j] 表示在表格 ij 列的答案
划分型动态规划:将序列不重不漏分成若干份,转移的时候考虑将 [i+1,j] 接在状态 dp[i] 后,形成状态 dp[j]
状态压缩动态规划:使用二进制 01 串来表示状态,表示维度通常不大。

习题……上面的都是!