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

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

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

坐标型 & 双序列型

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

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

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

LC 62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

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

计算样例 3 行 7 列的方案数，动态规划的状态表格为：

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[n + 1][m + 1];

        memset(dp, 0, sizeof(dp));
        dp[0][1] = 1;

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] ;
            }
        return dp[n][m];
    }
};

class Solution {

public:

int uniquePaths(int m, int n) {

int dp[n + 1][m + 1];

memset(dp, 0, sizeof(dp));

dp[0][1] = 1;

for (int i = 1; i <= n; i++)

for (int j = 1; j <= m; j++){

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] ;

}

return dp[n][m];

}

};

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

LC 1143. 最长公共子序列

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

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

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

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

状态表示： $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 推出的动态规划状态表格为：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.length(), m = text2.length();
        int dp[n + 1][m + 1];

        memset(dp, 0, sizeof(dp));

        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                if (text1[i - 1] == text2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else 
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[n][m];
    }
};

class Solution {

public:

int longestCommonSubsequence(string text1, string text2) {

int n = text1.length(), m = text2.length();

int dp[n + 1][m + 1];

memset(dp, 0, sizeof(dp));

for (int i = 1; i <= n; i++){

for (int j = 1; j <= m; j++){

if (text1[i - 1] == text2[j - 1])

dp[i][j] = dp[i - 1][j - 1] + 1;

else

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

}

return dp[n][m];

}

};

划分型动态规划

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

这样的题目在 LeetCode 里面也很经典：132. 分割回文串 II、410. 分割数组的最大值、1278. 分割回文串 III、1335. 工作计划的最低难度。

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

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

LC 132. 分割回文串 II

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

示例:

输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

示例:

输入: "aab"

输出: 1

解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

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

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

class Solution {
public:
    bool check(int x, int y, string s){
        for (int i = x; i <= y; i++){
            if (s[i - 1] != s[y + x - i - 1]) return false;
        }
        return true;
    }
    int minCut(string s) {
        int n = s.length();
        int dp[n + 1];

        memset(dp, -1, sizeof(dp));
        dp[0] = 0;

        for (int i = 1; i <= n; i++){
            for (int j = 0; j < i; j++){
                if (dp[j] == -1 || !check(j+1, i, s)) continue;
                if (dp[i] == -1 || dp[i] > dp[j] + 1) dp[i] = dp[j] + 1;
            }
        }

        return dp[n] - 1;
    }
};

class Solution {

public:

bool check(int x, int y, string s){

for (int i = x; i <= y; i++){

if (s[i - 1] != s[y + x - i - 1]) return false;

}

return true;

}

int minCut(string s) {

int n = s.length();

int dp[n + 1];

memset(dp, -1, sizeof(dp));

dp[0] = 0;

for (int i = 1; i <= n; i++){

for (int j = 0; j < i; j++){

if (dp[j] == -1 || !check(j+1, i, s)) continue;

if (dp[i] == -1 || dp[i] > dp[j] + 1) dp[i] = dp[j] + 1;

}

return dp[n] - 1;

}

};

状态压缩动态规划

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

状态压缩动态规划的特点就是使用一个数的二进制形式保存状态，比如，$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$ 为变成 $0$：bits&~(1<<j)

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

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

LC

给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），就用 '#' 表示；否则，用 '.' 表示。

学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的一起参加考试且无法作弊的最大学生人数。

学生必须坐在状况良好的座位上。

示例 1：
输入：seats = [["#",".","#","#",".","#"],
              [".","#","#","#","#","."],
              ["#",".","#","#",".","#"]]
输出：4
解释：教师可以让 4 个学生坐在可用的座位上，这样他们就无法在考试中作弊。

给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），就用 '#' 表示；否则，用 '.' 表示。

学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的一起参加考试且无法作弊的最大学生人数。

学生必须坐在状况良好的座位上。

示例 1：

输入：seats = [["#",".","#","#",".","#"],

[".","#","#","#","#","."],

["#",".","#","#",".","#"]]

输出：4

解释：教师可以让 4 个学生坐在可用的座位上，这样他们就无法在考试中作弊。

状态表示： $dp[i][bits]$ 表示第 $i$ 行座位情况为 $bits$ 前 $i$ 合法状态下最多坐多少人。（$bits$ 中 $0$ 表示没人坐；$1$ 表示有人坐）
边界：$dp[0][0]= 0$
状态转移：$dp[i][bits_{cur}]=max(dp[i][bits_{cur}],dp[i−1][bits_{pre}]+bitcount(bits_{cur}))$ 且 $i$ 行 $bits_{cur}$，$i-1$ 行 $bits_{pre}$ 合法：

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

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

<br /><br />class Solution {
public:
    int bcount(int x){ for (int ret = 0; ; x -= x&-x, ++ret) if (x == 0) return ret; }

    int maxStudents(vector<vector<char>>& seats) {
        int n = seats.size(), m = seats[0].size();
        int dp[n + 1][1<<m];

        memset(dp, -1, sizeof(dp));
        dp[0][0] = 0;

        int lim = (1 << m);
        for (int i = 1; i <= n; i++){
            for (int cur = 0; cur < lim; cur++){
                for (int pre = 0; pre < lim; pre++){
                    if (dp[i - 1][pre] == -1) continue; // 第 i - 1 行作为情况做 pre 的方案不存在

                    bool flag = true;
                    for (int j = 0; j < m; j++){
                        if (((cur>>j)&1) == 0) continue; // 如果这个位置没人坐，不用检查了
                        if (seats[i - 1][j] == '#') flag = false; // 有人坐，但椅子坏了
                        if (j >= 1 && ((cur>>(j - 1))&1)) flag = false; // 有人坐，但左边有人
                        if (j + 1 < m && ((cur>>(j + 1))&1)) flag = false; // 有人坐，但右边有人
                        if (j >= 1 && ((pre>>(j - 1))&1)) flag = false; // 有人坐，但左前有人
                        if (j + 1 < m && ((pre>>(j + 1))&1)) flag = false; // 有人坐，但右前有人
                    }
                    if (flag == false) continue;

                    dp[i][cur] = max(dp[i][cur], dp[i - 1][pre] + bcount(cur));
                }
            }
        }

        int ans = 0;
        for (int s = 0; s < lim; s++) ans = max(ans, dp[n][s]);
        return ans;
    }
};

<br /><br />class Solution {

public:

int bcount(int x){ for (int ret = 0; ; x -= x&-x, ++ret) if (x == 0) return ret; }

int maxStudents(vector<vector<char>>& seats) {

int n = seats.size(), m = seats[0].size();

int dp[n + 1][1<<m];

memset(dp, -1, sizeof(dp));

dp[0][0] = 0;

int lim = (1 << m);

for (int i = 1; i <= n; i++){

for (int cur = 0; cur < lim; cur++){

for (int pre = 0; pre < lim; pre++){

if (dp[i - 1][pre] == -1) continue; // 第 i - 1 行作为情况做 pre 的方案不存在

bool flag = true;

for (int j = 0; j < m; j++){

if (((cur>>j)&1) == 0) continue; // 如果这个位置没人坐，不用检查了

if (seats[i - 1][j] == '#') flag = false; // 有人坐，但椅子坏了

if (j >= 1 && ((cur>>(j - 1))&1)) flag = false; // 有人坐，但左边有人

if (j + 1 < m && ((cur>>(j + 1))&1)) flag = false; // 有人坐，但右边有人

if (j >= 1 && ((pre>>(j - 1))&1)) flag = false; // 有人坐，但左前有人

if (j + 1 < m && ((pre>>(j + 1))&1)) flag = false; // 有人坐，但右前有人

}

if (flag == false) continue;

dp[i][cur] = max(dp[i][cur], dp[i - 1][pre] + bcount(cur));

}

int ans = 0;

for (int s = 0; s < lim; s++) ans = max(ans, dp[n][s]);

return ans;

}

};

Take Home Message

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

一	二	三	四	五	六	日
				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

WNJXYKの博客

喂你脚下有坑