正文
4、例题
对于动态规划题目来说，使用自上而下的思想解题相对来说是比较简单的
但是为了帮助大家更好地掌握动态规划的题目，以下例题都会使用更难的自下而上的思路进行分析
（1）最长递增子序列 | leetcode300
给定一个整数数组，找出其中最长严格递增子序列的长度（子序列是不要求连续的）
class Solution { public: int lengthOfLIS(vector<int>& nums) { // 特判 int n = nums.size(); if (n == 0) { return 0; } // 定义数组，dp[i] 表示以 nums[i] 结尾的子问题的结果，即最长严格递增子序列的长度，0 <= i <= n - 1 int dp[n]; // 填充数组 // 边界情况，dp[0] 表示以 nums[0] 结尾的子问题的结果，为一，因为有且只有一个元素 dp[0] = 1; // 填充数组 // 其余情况，从上往下、从左往右填充 for (int i = 1; i < n; i++) { dp[i] = 1; // 遍历选择 for (int j = 0; j < i; j++) { if (nums[j] < nums[i] ) { dp[i] = max(dp[i] , dp[j] + 1); } } } // 返回结果 return *std::max_element(dp, dp + n); } };
（2）最长公共子序列 | leetcode1143
给定两个字符串，找出它们最长公共子序列的长度（子序列是不要求连续的）
class Solution { public: int longestCommonSubsequence(string text1, string text2) { // 特判 int m = text1.size(); int n = text2.size(); if (m == 0) { return 0; } if (n == 0) { return 0; } // 定义数组，dp[i][j] 表示当 text1 长度为 i 且 text2 长度为 j 时子问题的结果，即最长公共子序列的长度，0 <= i <= m，0 <= j <= n int dp[m + 1][n + 1]; // 填充数组 // 边界情况，dp[i][0] 表示当 text1 长度为 i 且 text2 长度为 0 时子问题的结果，为零，因为 text2 字符串长度为零 // dp[0][j] 表示当 text1 长度为 0 且 text2 长度为 j 时子问题的结果，为零，因为 text1 字符串长度为零 for (int i = 0; i <= m; i++) { dp[i][0] = 0; } for (int j = 0; j <= n; j++) { dp[0][j] = 0; } // 填充数组 // 其余情况，从上往下、从左往右填充 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; 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[m][n]; } };
（3）最长回文子序列 | leetcode516
给定一个字符串，找出其中最长回文子序列的长度（子序列是不要求连续的）
class Solution { public: int longestPalindromeSubseq(string s) { // 特判 int n = s.size(); if (n == 0) { return 0; } // 定义数组，dp[i][j] 表示以 s[i] 开头且 s[j] 结尾的子问题的结果，即最长回文子序列的长度，0 <= i <= j <= n int dp[n][n]; memset(dp, 0, sizeof(dp)); // 填充数组 // 边界情况，dp[i][i] 表示以 s[i] 开头且 s[i] 结尾的子问题的结果，为一，因为有且只有一个元素 for (int i = 0; i < n; i++) { dp[i][i] = 1; } // 填充数组 // 其余情况，从下往上、从左往右填充 for (int i = n - 2; i >= 0; i--) { for (int j = i + 1; j < n; j++) { // 分类讨论 if (s[i] == s[j]) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); } } } // 返回结果 return dp[0][n - 1]; } };
（4）高楼扔鸡蛋 | leetcode887
class Solution { public: int superEggDrop(int k, int n) { // 特判 if ( k <= 1 || n <= 1 ) { return n; } // 定义数组，dp[i][j] 表示当鸡蛋数为 i 且楼层数为 j 时子问题的结果，即确定在最坏情况下鸡蛋掉落不会碎的最高楼层的操作次数 int dp[k + 1][n + 1]; // 填充数组 // 边界情况，dp[i][0] 表示当鸡蛋数为 i 且楼层数为 0 时子问题的结果，只需随便返回 0，因为此情况不合法 // dp[0][j] 表示当鸡蛋数为 0 且楼层数为 j 时子问题的结果，只需随便返回 0，因为此情况不合法 // dp[i][1] 表示当鸡蛋数为 i 且楼层数为 1 时子问题的结果，因为楼层数为 1，所以只需在第一层楼层尝试即可，因此最小操作次数为 1 // dp[1][j] 表示当鸡蛋数为 1 且楼层数为 j 时子问题的结果，因为鸡蛋数为 1，所以只能从低到高楼层逐层尝试，因此最小操作次数为 j for (int i = 0; i <= k; i++) { dp[i][0] = 0; dp[i][1] = 1; } for (int j = 0; j <= n; j++) { dp[0][j] = 0; dp[1][j] = j; } // 填充数组 // 其余情况，从上往下、从左往右填充 for (int i = 2; i<= k; i++) { for (int j = 2; j <= n; j++) { // 遍历选择 // 当鸡蛋数为 i 且楼层数为 j 时，因为不知道在哪一层扔鸡蛋符合条件，所以需要逐一尝试在每一层扔鸡蛋的情况 int result = INT_MAX; for (int k = 1; k <= j; k++) { // 如果鸡蛋碎了，说明在 k 层及以上的楼层扔鸡蛋也会碎 // 此时鸡蛋数量减一，之后继续检查 k 层以下的楼层即可，即状态转移为：dp[i - 1][k - 1] int case1 = dp[i - 1][k - 1] + 1; // 如果鸡蛋没碎，说明在 k 层及以下的楼层扔鸡蛋也不碎 // 此时鸡蛋数量不变，之后继续检查 k 层以上的楼层即可，即状态转移为：dp[i][j - k] int case2 = dp[i][j - k] + 1; // max 对应最坏情况 // min 对应最少次数 result = min(result, max(case1, case2)); } dp[i][j] = result; } } // 返回结果 return dp[k][n]; } };
class Solution { public: int superEggDrop(int k, int n) { // 特判 if ( k <= 1 || n <= 1 ) { return n; } // 定义数组，dp[i][j] 表示当鸡蛋数为 i 且楼层数为 j 时子问题的结果，即确定在最坏情况下鸡蛋掉落不会碎的最高楼层的操作次数 int dp[k + 1][n + 1]; // 填充数组 // 边界情况，dp[i][0] 表示当鸡蛋数为 i 且楼层数为 0 时子问题的结果，只需随便返回 0，因为此情况不合法 // dp[0][j] 表示当鸡蛋数为 0 且楼层数为 j 时子问题的结果，只需随便返回 0，因为此情况不合法 // dp[i][1] 表示当鸡蛋数为 i 且楼层数为 1 时子问题的结果，因为楼层数为 1，所以只需在第一层楼层尝试即可，因此最小操作次数为 1 // dp[1][j] 表示当鸡蛋数为 1 且楼层数为 j 时子问题的结果，因为鸡蛋数为 1，所以只能从低到高楼层逐层尝试，因此最小操作次数为 j for (int i = 0; i <= k; i++) { dp[i][0] = 0; dp[i][1] = 1; } for (int j = 0; j <= n; j++) { dp[0][j] = 0; dp[1][j] = j; } // 填充数组 // 其余情况，从上往下、从左往右填充 for (int i = 2; i<= k; i++) { for (int j = 2; j <= n; j++) { // 修改之处 // 当鸡蛋数为 i 且楼层数为 j 时，可以用二分搜索来查找楼层，代替线性搜索 int result = INT_MAX; int lp = 1; int rp = j; while (lp <= rp) { // 找出中间楼层 m int m = lp + (rp - lp) / 2; // 如果鸡蛋碎了，说明在 m 层及以上的楼层扔鸡蛋也会碎 // 此时鸡蛋数量减一，之后继续检查 m 层以下的楼层即可 int case1 = dp[i - 1][m - 1] + 1; // 如果鸡蛋没碎，说明在 m 层及以下的楼层扔鸡蛋也不碎 // 此时鸡蛋数量不变，之后继续检查 m 层以上的楼层即可 int case2 = dp[i][j - m] + 1; // 缩小搜索区间 if (case1 > case2) { rp = m - 1; } else { lp = m + 1; } // max 对应最坏情况 // min 对应最少次数 result = min(result, max(case1, case2)); } dp[i][j] = result; } } // 返回结果 return dp[k][n]; } };
（5）正则表达式 | leetcode10
class Solution { public: bool isMatch(string s, string p) { // 预处理 // 字符串 s 和字符串 p 前填充一个无关字符，此时 dp[i][j] 可以直接表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配 int m = s.size(); int n = p.size(); s.insert(0, "_"); p.insert(0, "_"); // 定义数组，dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配 bool dp[m + 1][n + 1]; // 填充数组 // 边界情况，dp[0][0] 表示 s 的前 0 个字符和 p 的前 0 个字符是否匹配，为 true ，因为两者都是空字符串 // dp[i][0] 表示 s 的前 i 个字符和 p 的前 0 个字符是否匹配，此时 p 为空字符串，只有 s 是空字符串才能匹配 // dp[0][j] 表示 s 的前 0 个字符和 p 的前 j 个字符是否匹配，此时 s 为空字符串，只有 p 是“字符+星号”组合才能匹配 dp[0][0] = true; for (int i = 1; i <= m; i++) { dp[i][0] = false; } for (int j = 1; j <= n; j++) { dp[0][j] = j % 2 == 0 && p[j] == '*' && dp[0][j - 2]; } // 填充数组 // 其余情况，从上往下、从左往右填充 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // 分类讨论 // 如果 p[j] 为字符且 s[i] != p[j]，那么 dp[i][j] 结果就等于 false // 如果 p[j] 为字符且 s[i] == p[j]，那么 dp[i][j] 结果取决于 dp[i - 1][j - 1] if ( p[j] != '.' && p[j] != '*' ) { dp[i][j] = s[i] == p[j] && dp[i - 1][j - 1]; } // 如果 p[j] 为点号，那么 p 中点号必然匹配 s 中一个字符，那么 dp[i][j] 结果取决于 dp[i - 1][j - 1] else if (p[j] == '.') { dp[i][j] = dp[i - 1][j - 1]; } // 如果 p[j] 为星号且 p 中“字符+星号”匹配 s 中零个字符，那么 dp[i][j] 结果取决于 dp[i][j - 2] // 如果 p[j] 为星号且 p 中“字符+星号”匹配 s 中一个字符，那么 dp[i][j] 结果取决于 dp[i - 1][j] else if (p[j] == '*') { dp[i][j] = dp[i][j - 2] || ((p[j - 1] == s[i] || p[j - 1] == '.') && dp[i - 1][j]); } } } // 返回结果 return dp[m][n]; } };
（6）编辑距离 | leetcode72
class Solution { public: int myMin(int a, int b, int c) { return min(min(a, b), c); } int minDistance(string word1, string word2) { // 特判 int m = word1.size(); int n = word2.size(); if (m == 0) { return n; } if (n == 0) { return m; } // 定义数组，dp[i][j] 表示当 A 长度为 i 且 B 长度为 j 时子问题的结果，即编辑距离 int dp[m + 1][n + 1]; // 填充数组 // 边界情况，dp[i][0] 表示当 A 长度为 i 且 B 长度为 0 时子问题的结果，为 i，只需对 A 做 i 次删除或对 B 做 i 次插入即可 // dp[0][j] 表示当 A 长度为 0 且 B 长度为 j 时子问题的结果，为 j，只需对 A 做 j 次插入或对 B 做 j 次删除即可 for (int i = 0; i < m + 1; i++) { dp[i][0] = i; } for (int j = 0; j < n + 1; j++) { dp[0][j] = j; } // 填充数组 // 其余情况，从上往下、从左往右填充 for (int i = 1; i < m + 1; i++) { for (int j = 1; j < n + 1; j++) { // 分类讨论 if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = myMin(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1); } } } // 返回结果 return dp[m][n]; } };
5、技巧
经过上面题目的练习，相信大家对解决动态规划问题都有一定的感悟
下面是从题目中总结的一些关键技巧，有些是规律性的总结，有些是对过程的优化
建议大家看完下面的总结后重新回顾下例题
（1）怎么定义 dp 函数或 dp 数组
常用的定义方法如下：
- 以 nums[i] 开头的子问题的结果
- 以 nums[i] 结尾的子问题的结果
- nums[0...i] 中的子问题的结果（从前往后数长度为 i 的数组中 子问题的结果）
- nums[i...n] 中的子问题的结果（从后往前数长度为 i 的数组中 子问题的结果）
（2）怎么推导 dp 函数或 dp 数组
推导过程的核心是数学归纳法：在已知 dp[1...k] 的情况下，求 dp[k + 1]
常用的推导思路如下：
- 在当前状态下，面临哪些选择，尝试所有选择并取最值
- 在当前状态下，满足哪些条件才能进行选择，对不同的条件分类讨论
对于自下而上的思路来说，推导的过程就是填充数组的过程
而填充数组就有两个方向：从上往下、从左往右；从下往上，从右往左
我们可以借助已知信息和待求信息，分析它们的相对位置，得出填充方向，具体来说：
- 思考：如果要求当前值，信息可以从什么方向获得
- 思考：如果要求目标值，怎么减小问题规模，怎么利用以前信息
（3）空间优化
动态规划是对时间复杂度的一种优化，一般来说，可以将时间复杂度降到多项式时间
但在动态规划的框架下，对于某些情况，还能使用滚动数组来对空间复杂度进行优化
使用滚动数组一般可以将二维数组压缩成一维数组，或者将一维数组压缩成常数
什么情况下才能使用滚动数组，以及滚动数组究竟要怎么用呢？
如果在填充数组的过程中，要求当前值只需要用到之前的某些值，那么我们就没必要保存完整的数组
而只需要用更小的数组保存以后需要的值就好，这就是滚动数组的思想
（4）记录过程
通过动态规划，我们可以求出问题的最值，但是我们能不能知道经过怎样的过程才能得到这个最值呢
答案是肯定的，不过我们需要对求解的过程做一些修改
一种思路是我们在填充数组时，不仅仅要记录结果值，还要记录到达此结果的路径
这样当到达目标值时，就能知道怎么到达这个目标的，这种方法返回结果快，但是需要额外的空间
而另一种思路是在填充数组时，还是只会记录结果值，当需要求路径时再通过某些方法回溯
这种方法返回结果会比较慢，但无需额外的存储空间保存路径
