第 19 关 | 经典刷题思想之动态规划 : 3.黄金挑战——继续盘点高频 DP 问题
动态规划是一个非常重要的问题，相关的题目也特别多，有了前面的基础，这里我们继续学习几道典型的动态规划问题。
| 关卡名 | 掌握一些高频动态规划问题 | 我会了✔️ | |
|---|---|---|---|
| 题目 | 1.最长回文串 | ✔️ | |
| 2.最少分割回文串 | ✔️ | ||
| 3.最长公共子序列 | ✔️ | ||
| 4.最小编辑距离 | ✔️ | ||
| 5.正则表达式 | ✔️ | ||
| 6.乘积最大的子数组 | ✔️ | ||
| 7.买卖股票最佳时机系列问题 | ✔️ | ||
| 8.打家劫舍问题 | ✔️ |
前面我们分析了一些稍微简单一些的题目的解决思路，但是动态规划题是可以分为很多种类型的，常见的有三种： 1.计数型：例如在路径选择中，问你从左上角到右下角有多少种走法，有多少种方法选出K个数使得和是Sum等等。 2.求最大最小值，这种题目是非常多的，占据了动态规划的大部分，常见有最大、最长、最多、最少等等。一般看到带”最“的，我们都要考虑一下该题是不是DP问题（滑动窗口的问题一般也带”最“，注意区分）。 3.求是否存在类型的，例如青蛙跳中，问你是否存在这样的路径，以及能不能选择K个数，使得和为Sum等等。 有些地方还会将DP问题分为 坐标型、序列型、划分型、区间型、双序列型等等。这个我们不必太关注 ，只要将常见的题目做会就行了。
1. 回文串专题
1.1. 最长回文串
LeetCode5.给你一个字符串 s，找到 s 中最长的回文子串。
示例1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
本题有很多种解法的，感兴趣的读者可以到LeetCode查一下，这里我们就看一下如何通过DP来解决。 我们仍然按照动态规划的几个步骤来解决。 第一步：确定状态 对于最优策略产生的最长回文子串T，长度是M，必然只有两种情况： ●情况1：回文串长度是1，即一个字母。 ●情况2：回文串长度大于1，那么必定有T[0]=T[M-1]
设T[0]是S[i]，T[M-1]是S[j],则T剩下的部分T[1...M-2]仍然是一个回文串，而且是S[i+1,j-1]最长回文子串。因此子问题就是：如要要求S[i..j]的最长回文子串，如果S[i]=S[j],需要知道S[i+1,..j-1]的最长回文子串。否则答案是S[i+1..j]的最长回文子串或S[i..j-1]的最长回文子串，这就是子问题。 状态：设f[i][j]为S[i..j]的最长回文子串的长度。
第二步：确认初始条件和边界情况 初始条件f[0][0]=f[1][1]=...=f[N-1][N-1]=1一个字母也是一个长度为1的回文串。 如果S[i]==S[i+1],f[i][i+1]=2 如果S[i]!=S[i+1],f[i][i+1]=1 第三步：计算顺序 这里不能按照i的顺序算，而应该按照j-i从小到大的顺序计算。这个比较绕，执行的顺序画成图就是这样的：
长度1：f[0][0],f[1][1],f[2][2]...f[N-1][N-1] 长度2：f[0][1],...f[N-2][N-1] ... 长度N：f[0][N-1] 答案是f[0][N-1] 本题的时间复杂度和空间复杂度都是O(N^2)
int longestPalindrome(string s) {
char arr[s.length()];
for (int i = 0; i < s.length(); i++) {
arr[i] = s[i];
}
int n = s.length();
if (n == 0) {
return 0;
}
int f[n][n];
int i, j = 0;
for (i = 0; i < n; i++) {
f[i][j] = 1;
}
for (i = 0; i < n - 1; i++) {
f[i][i + 1] = (arr[i] == arr[i + 1]) ? 2 : 1;
}
for (int len = 3; len <= n; len++) {
for (i = 0; i <= n - len; i++) {
j = i + len - 1;
f[i][j] = max(f[i][j - 1], f[i + 1][j]);
if (arr[i] == arr[j]) {
f[i][j] = max(f[i][j], f[i + 1][j - 1] + 2);
}
}
}
return f[0][n - 1];
}
public int longestPalindrome(String ss) {
char[] s = ss.toCharArray();
int n = s.length;
if (n == 0) {
return 0;
}
int[][] f = new int[n][n];
int i, j=0;
for (i = 0; i < n; i++) {
f[i][i] = 1;
}
for (i = 0; i < n - 1; i++) {
f[i][i + 1] = (s[i] == s[i + 1]) ? 2 : 1;
}
for (int len = 3; len <= n; len++) {
for (i = 0; i <= n - len; i++) {
j = i + len - 1;
f[i][j] = Math.max(f[i][j - 1], f[i + 1][j]);
if (s[i] == s[j]&&f[i + 1][j - 1]==j-i-1) {
f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + 2);
}
}
}
return f[0][n - 1];
}
def longestPalindrome(s):
n = len(s)
if n == 0:
return 0
dp = [[0] * (n+1) for _ in range(n+1)]
for i in range(n):
dp[i][i] = 1
for i in range(1, n):
dp[i][i+1] = s[i] == s[i+1] and 2 or 1
for len_ in range(3, n+1):
for i in range(0, n-len_):
j = i + len_ - 1
dp[i][j] = max(dp[i][j-1], dp[i+1][j])
if s[i] == s[j]:
dp[i][j] = max(dp[i][j], dp[i+1][j-1]+2)
return dp[0][n-1]
1.2. 最少分隔回文串
leetcode.132 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。返回符合要求的 最少分割次数 。
示例1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
我们在回溯章节讲解过简单的分割问题，就是统计一定能分割出多少种来，我们自然可以先找到所有的，然后再返回最短的，但是这样的效率太低了，我们考虑如何使用DP来优化一下。 第一步：确定状态 我们还是先看最优策略中最后一段回文串，设为S[j...N-1]，需要知道S前j个字符[0...j-1]最少可以划分成几个回文串。因此求S前N个字符串就变成前j-1个，这就是子问题。
由此， 我们也确定出了状态：设f[i]为前i个字符S[0...i-1]最少可以划分成f[j]个回文串。 由此也确定了状态转移方程：
判断初始条件 空串可以分为0个回文串，f[0]=0。 然后依次计算f[0],f[1]，...f[N]。 第四步：开始计算 这里还有个额外的问题就是如何判断回文串。我们前面介绍过对撞型双指针，可以从两头向中间判断即可。但是这样的话，由于范围不确定，因此每个位置都要进行大量的尝试才可以，效率太低了，能否简化一下呢？ 我们观察到回文串就奇数和偶数两种方式：
这里我们可以换了思维，采用生成的方式，从中间开始向两边扩展，每次都在左右两端加上同样的字符。当发现某个位置与我们预期的不一致时就停下来，这样我们就能快速找到某个位置开始的所有回文串。本题也是难得一见的”分手型双指针“。 因此，我们采取的策略就是从S每一个字符开始向两边扩展，当然要同时考虑奇数和偶数回文的情况。本题我们还需要使用isPalin[i][j]表示S[i...j]是否是回文串。 因此本题就S最少划分成多少个回文串就是：
答案是f[N]-1，因为原题是求最少划分几次。
public int minCut(String ss) {
char[] s = ss.toCharArray();
int n = s.length;
if (n == 0) {
return 0;
}
boolean[][] isPalin = new boolean[n][n];
int[] f = new int[n + 1];
int i, j, t;
for (i = 0; i < n; i++) {
for (j = i; j < n; j++) {
isPalin[i][j] = false;
}
}
//生成回文串
for (t = 0; t < n; t++) {
//奇数长度
i = j = t;
while (i >= 0 && j < n && s[i] == s[j]) {
isPalin[i][j] = true;
i--;
j++;
}
//偶数长度
i = t;
j = t + 1;
while (i >= 0 && j < n && s[i] == s[j]) {
isPalin[i][j] = true;
i--;
j++;
}
}
f[0] = 0;
for (i = 1; i <= n; i++) {
f[i] = Integer.MAX_VALUE;
for (j = 0; j < i; j++) {
if (isPalin[j][i - 1]) {
f[i] = Math.min(f[i], f[j] + 1);
}
}
}
return f[n] - 1;
}
public int minCut(String ss) {
char[] s = ss.toCharArray();
int n = s.length;
if (n == 0) {
return 0;
}
boolean[][] isPalin = new boolean[n][n];
int[] f = new int[n + 1];
int i, j, t;
for (i = 0; i < n; i++) {
for (j = i; j < n; j++) {
isPalin[i][j] = false;
}
}
//生成回文串
for (t = 0; t < n; t++) {
//奇数长度
i = j = t;
while (i >= 0 && j < n && s[i] == s[j]) {
isPalin[i][j] = true;
i--;
j++;
}
//偶数长度
i = t;
j = t + 1;
while (i >= 0 && j < n && s[i] == s[j]) {
isPalin[i][j] = true;
i--;
j++;
}
}
f[0] = 0;
for (i = 1; i <= n; i++) {
f[i] = Integer.MAX_VALUE;
for (j = 0; j < i; j++) {
if (isPalin[j][i - 1]) {
f[i] = Math.min(f[i], f[j] + 1);
}
}
}
return f[n] - 1;
}
def minCut(s):
n = len(s)
if n == 0:
return 0
isPalin = [False] * n
f = [0] * (n + 1)
f[0] = 0
for i in range(n):
for j in range(i):
if s[i] == s[j]:
isPalin[i] = True
break
for i in range(1, n + 1):
f[i] = f[i - 1] if isPalin[i - 1] else INT_MAX
return f[n]
s = "aba" # 这里使用了一个例子字符串作为输入，可以根据实际情况进行修改和测试。
print(minCut(s)) # 输出最小割的大小，根据输入的字符串可能为0或正整数。
2. 双串典型问题
上面的所有例子都是针对一个串或者一个序列的，如果换成两个串StrA和StrB该怎么办呢？最基本的思路仍然是逐步将问题 的规模缩小，我们尝试将将StrA缩小一个，或者将StrB缩小一个，或者同时缩小。 有几个热门的双串问题，我们一起来研究一下。
2.1. 最长公共子序列
这也是一道非常重要的问题，针对两个序列的DP问题，这种一般可以转化为二维动态规划。 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
分析：公共子串一定是对应的字符按照顺序都相等，找到最长的对应对子，并且子连线不能相交，如下图所示。
对于本题，我们设A的长度为m，B的长度为n，现在我们考虑最优策略产生出的最长公共子串（虽然还不知道是什么），但是对于最后一步，我们知道：可以观察A[m-1]和B[m-1]这两个字符是否作为一个对子在最优策略中。无非就三种情况，对子中没有A[m-1]，或者没有B[n-1]，或者 第一种，假如对子中没有A[m-1],如下:
这时候可以放心的将A[m-1]扔掉不管，只看A的前m-1个字符。此时A和B的最长公共子串就是A的前m-1个字符和B前n个字符的最长公共子串。 第二种 ，对称的，第二种情况就是对子中没有B[n-1]的情况，此时A和B的最长公共子串就是A前m个与B的前n-1个字符的最长公共子串。也就是如下所示：
第三种情况就是，对子中有A[m-1]和B[n-1]，此时情况如下图所示，
此时AheadB的最长公共子串就是A前m-1ge 字符和B的前n-1个字符的最长公共子串+A[m-1] 思考此时为什么不用考虑A[m-1]和B[n-1]都不在？ 这样我们就找到了子问题：原来要求的是A[0...m-1]和B[0..n-1]的最长公共子串，现在是将A减少了一个，或者将B减少了一个，具体来说就是将其变成了要求A[0..m-1]和B[0..n-2]的最长公共子串，A[0..m-2]和B[0..n-1]的最长公共子串和A[0..m-2]和B[0..m-2]的最长公共子串。 状态就是：设f[i][j]为A前i个字符A[0..i-1]和B前j个字符[0..j-1]的最长公共子串的长度，求f[i][j]。 注意这里的i是A的前一个字符，j代表的是B的前j个字符串。
然后我们再来看初始条件和边界条件。 初始条件： f[0][j]=0,j=0..n f[i][0]=0,i=0..m 计算顺序就是 f[0][0],f[0][1],...,f[0][n] f[1][0],f[1][1],...,f[1][n] ... f[m][0],f[m][1],...,f[m][n] 最后求的就是f[m][n]
public int longestCommonSubsequence(String A, String B) {
int m = A.length();
int n = B.length();
int i, j;
int[][] f = new int[2][n + 1];
int old, now = 0;
for (i = 0; i <= n; i++) {
f[now][i] = 0;
}
for (i = 1; i <= m; i++) {
old = now;
now = 1 - now;
for (j = 0; j <= n; j++) {
f[now][j] = f[old][j];
if (j > 0) {
f[now][j] = Math.max(f[now][j], f[now][j - 1]);
}
if (j > 0 && A.charAt(i - 1) == B.charAt(j - 1)) {
f[now][j] = Math.max(f[now][j], f[old][j - 1] + 1);
}
}
}
return f[now][n];
}
def longestCommonSubsequence(A, B):
m = len(A)
n = len(B)
f = [[0] * (n+1) for _ in range(m+1)]
i, j = 1, 1
for i in range(m+1):
for j in range(n+1):
if i == 1 and j == 1:
f[i][j] = 0
elif A[i-1] == B[j-1]:
f[i][j] = f[i-1][j-1] + 1
else:
f[i][j] = max(f[i-1][j], f[i][j-1])
return f[m][n]
int longestCommonSubsequence(string A, string B) {
int m = A.length();
int n = B.length();
int i, j;
int[][] f = new int[2][n + 1];
int old, now = 0;
for (i = 0; i <= n; i++) {
f[now][i] = 0;
}
for (i = 1; i <= m; i++) {
old = now;
now = 1 - now;
for (j = 0; j <= n; j++) {
f[now][j] = f[old][j];
if (j > 0) {
f[now][j] = max(f[now][j], f[now][j - 1]);
}
if (j > 0 && A[i - 1] == B[j - 1]) {
f[now][j] = max(f[now][j], f[old][j - 1] + 1);
}
}
}
return f[now][n];
}
2.2. 编辑距离
LeetCode72.给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
设A长度为m，B的长度为n，全部操作完后A的长度也是n，并且A[n-1]=B[n-1]。于是最优策略（以及所有合法策略）最终都是让A的最后一个字符变成B的最后一个字符。 我们还是先看最后一个位置，如果想让A的最后一个变成B的最后一个有几种方法呢？无非那么几种：
- 情况1：A在最后插入B[n-1],如下所示，此时只要将A[0..m-1]变成B[0..n-2]：
- 情况2：在A的最后将一个字符替换成B[n-1]，此时要将A[0..m-2]变成B[0..n-2]
情况3:是删掉A的最后一个字符，此时直接将A[0..m-2]变成B[0..n-1] 最后一种情况是，假如A和B的最后一个字符相等，此时就什么都不用做了。只需将剩下的A[0..m-2]变成B[0..n-2]即可。 由此我们就得到了子问题的表述：原来是求A[0..m-1]和B[0..n-1]的最小编辑距离，而现在变成了求A[0..m-1]和B[0..n-2]的最小编辑距离，A[0..m-2]和B[0..n-1]的最小编辑距离或者A[0..m-2]和B[0..n-2]的最小编辑距离。
状态就是：设f[i][j]为A前i个字符A[0..i-1]和B前j个字符B[0..j-1]的最小编辑距离。 初始条件：一个空串和一个长度为L的串的最小编辑距离为L。 f[0][j]=j(j=0,1,2,..,n) f[i][0]=i(i=0,1,2,..,m) 计算顺序就是 f[0][0],f[0][1],...,f[0][n] f[1][0],f[1][1],...,f[1][n] ... f[m][0],f[m][1],...,f[m][n] 最后求的就是f[m][n] 实现代码：
public int minDistance(String ss1, String ss2) {
char[] s1 = ss1.toCharArray();
char[] s2 = ss2.toCharArray();
int m = s1.length;
int n = s2.length;
int i, j, k;
int[][] f = new int[m + 1][n + 1];
for (j = 0; j <= n; j++) {
f[0][j] = j;
}
for (i = 1; i <= m; i++) {
f[i][0] = i;
for (j = 1; j <= n; j++) {
f[i][j] = Math.min(f[i - 1][j] + 1, f[i - 1][j - 1] + 1);
f[i][j] = Math.min(f[i][j], f[i][j - 1] + 1);
if (s1[i - 1] == s2[j - 1]) {
f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
}
}
}
return f[m][n];
}
int minDistance(string s1, string s2) {
int m = s1.length();
int n = s2.length();
vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));
for (int j = 0; j <= n; j++) {
f[0][j] = j;
}
for (int i = 1; i <= m; i++) {
f[i][0] = i;
for (int j = 1; j <= n; j++) {
f[i][j] = min(f[i - 1][j] + 1, f[i - 1][j - 1] + 1);
f[i][j] = min(f[i][j], f[i][j - 1] + 1);
if (s1[i - 1] == s2[j - 1]) {
f[i][j] = min(f[i][j], f[i - 1][j - 1]);
}
}
}
return f[m][n];
}
def minDistance(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
elif s1[i - 1] < s2[j - 1]:
dp[i][j] = dp[i - 1][j] + 1
else:
dp[i][j] = dp[i][j - 1] + 1
return dp[m][n]
2.3. 正则表达式匹配
LeetCode10.给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '' 的正则表达式匹配。 '.' 匹配任意单个字符'' 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例2：
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
我们分析发现有那么几种情况，
- 如果B[n-1]是一个正常字符(不是.或者*)，则如果A[m-1]=B[n-1]，能否匹配取决于A[0..m-2]和B[0..n-2]是否匹配，否则不能匹配。
- 如果B[n-1]是‘.’，则A[m-1]一定是和‘.’匹配，之后能否匹配取决于A[0..m-2]和B[0..n-2]。
- 如果B[n-1]是' '，则代表B[n-2]=c可以重复0次或者多测，它们是一个整体C，需要考虑A[m-1]是0个从，还是多个c中的最后一个。
-
- 如果A[m-1]是0个C，能否匹配取决于A[0..m-1]和B[0...n-3]是否匹配。
- A[m-1]是多个c中的最后一个，能否匹配取决于A[0..m-2]和B[0..n-1]是否匹配，这种情况必须A[m-1]=c或者c='.'
归结起来就是我们要求的子问题：需要知道A前m个字符和B前n-1个字符，A的前m-1个字符和B的前n个字符以及A前m个字符和B的前N-2个字符能否匹配。 状态就是：设f[i][j]为A前i个字符A[0..i-1]和B前j个字符B[0..j-1]能否匹配。 此时的状态转移方程就是： 初始条件和边界情况：空串和空正则表达式匹配：f[0][0]=TRUE 空的正则表达式不能匹配长度>0的串 f[1][0]=...=f[m][0]=FALSE 注意f[0][1..n]也用动态规划计算，但是因为没有A[-1]，所以只能用第二种情况中的f[i][j-2] 计算顺序就是 f[0][0],f[0][1],...,f[0][n] f[1][0],f[1][1],...,f[1][n] ... f[m][0],f[m][1],...,f[m][n] 最后求的就是f[m][n] 实现代码就是：
public boolean isMatch(String ss1, String ss2) {
char[] s1 = ss1.toCharArray();
char[] s2 = ss2.toCharArray();
int m = s1.length;
int n = s2.length;
int i, j;
boolean[][] f = new boolean[m + 1][n + 1];
for (i = 0; i <= m; i++) {
f[i][0] = (i == 0);
for (j = 1; j <= n; j++) {
f[i][j] = false;
if (s2[j - 1] != '*') {
if (i > 0 && (s2[j - 1] == '.' || s2[j - 1] == s1[i - 1])) {
f[i][j] |= f[i - 1][j - 1];
}
} else {
if (j - 2 >= 0) {
f[i][j] |= f[i][j - 2];
}
if (i > 0 && j - 2 >= 0 && (s2[j - 2] == '.' || s2[j - 2] == s1[i - 1])) {
f[i][j] |= f[i - 1][j];
}
}
}
}
return f[m][n];
}
bool isMatch(string s1, string s2) {
char s1[] = s1.c_str();
char s2[] = s2.c_str();
int m = s1.length();
int n = s2.length();
bool (*f)[n + 1] = new bool[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
f[i][0] = (i == 0);
for (int j = 1; j <= n; j++) {
f[i][j] = false;
if (s2[j - 1] != '*') {
if (i > 0 && (s2[j - 1] == '.' || s2[j - 1] == s1[i - 1])) {
f[i][j] |= f[i - 1][j - 1];
}
} else {
if (j - 2 >= 0) {
f[i][j] |= f[i][j - 2];
}
if (i > 0 && j - 2 >= 0 && (s2[j - 2] == '.' || s2[j - 2] == s1[i - 1])) {
f[i][j] |= f[i - 1][j];
}
}
}
}
return f[m][n];
}
def isMatch(s1, s2):
m = len(s1)
n = len(s2)
f = [[False] * (n + 1) for _ in range(m + 1)]
# 初始化f[0][0]为True，表示空字符串和空字符串匹配
f[0][0] = True
for i in range(1, m + 1):
if s1[i - 1] == '*':
# 如果s1[i-1]为*，则更新f[i][j]为f[i-1][j-2]|f[i-1][j]（若s2[j-2]和s2[j-1]与s1[i-1]匹配）
f[i][0] = f[i - 1][0]
f[i][0] |= f[i - 1][1] & f[i - 1][0] & f[i - 1][2] & ... & f[i - 1][n - 3] & f[i - 1][n - 2] & f[i - 1][n - 1]
else:
# 如果s1[i-1]不为*，则更新f[i][j]为f[i-1][j-1]|f[i-1][j]（若s2[j-1]与s1[i-1]匹配）
f[i][0] = f[i - 1][0] | f[i - 1][1] | f[i - 1][2] | ... | f[i - 1][n - 3] | f[i - 1][n - 2] | f[i - 1][n - 1]
# 遍历s2，判断是否匹配
for j in range(1, n + 1):
if s2[j - 1] == '*':
# 如果s2[j-1]为*，则更新f[i][j]为f[i][j-2]|f[i][j-1]|f[i][j+2]|...|f[i][n-3]|f[i][n-2]|f[i][n-1]（若s2[j-2]和s2[j-1]，s2[j+2]，...，s2[n-3]，s2[n-2]，s2[n-1]与s1的任意字符匹配）
for i in range(0, m + 1):
if s2[j - 2] == '.' or s2[j - 2] == s1[i - 1]:
f[i][j] = f[i][j - 2] | f[i][j - 1] | f[i][j + 2] | ... | f[i][n - 3] | f[i][n - 2] | f[i][n - 1]
else:
# 如果s2[j-1]不为*，则更新f[i][j]为f[i][j-1]|f[i][j]|（若s2[j-1]与s1的任意字符匹配）
for i in range(0, m + 1):
if s2[j - 1] == s1[i - 1]:
f[i][j] = f[i][j - 1] | f[i][j]
# 检查最长公共前缀匹配的长度是否等于m，如果是则返回True，否则返回False
return f[-1][-1] == m
与本题非常类似的还有个通配符匹配的问题LeetCode44，感兴趣的同学可以研究一下。
3. 乘积最大的子数组
LeetCode152.给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。子数组就是数组的连续子序列的意思。
示例1：
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例2：
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
本题与上面《最长连续递增子序列》的思路和解法都非常类似，但是难度稍微大一些。我们仍然采用前面的步骤来解决。 第一步：确定状态和子问题 我们先看最后一步，对于最优策略(乘积最大)，一定有最后一个元素a[j]。我们看看a[j]会有几种情况：
- 第一种：最优策略就是一个元素{a[j]}，结果也是a[j]
- 第二种：连续子序列长度大约1，那么最优策略中a[j]前一个元素肯定是a[j-1]。因为存在负负得正的问题，我们需要进一步讨论：
-
- 如果a[j]是正数，我们希望以a[j-1]结尾的连续子序列乘积最大。
- 如果a[j]是负数，我们希望以a[j-1]结尾的连续子序列乘积最小。
所以我们需要同时保留两个极值。为此，我们可以当成两个问题来做，求以a[j]结尾的连续子序列的最大乘积和以a[j]结尾的连续子序列的最小乘积。这两种情况都需要求以a[j-1]结尾的乘积最大/小连续子序列。 子问题： 设f[j]=以a[j]结尾的连续子序列的最大乘积，设g[j]=以g[j]结尾的连续子序列的最小乘积。
则f[j]求最大乘积的状态转移方程就是：
则g[j]求最大乘积的状态转移方程就是：
第二步：确认初始条件和边界情况 观察上面的关系式，很明显必须j-1>=0，也就是j>=1，也就是在a[j]前面至少还有一个元素。 第三步：按顺序计算 这里有g[j]和f[j]两个数组，分别表示最大和最小乘积 ，因此我们依次计算就好了。 结果是 max{f[0],g[0]，f[1],g[1]，f[2],g[2]....f[n-1],g[n-1]} 第四步：编码实现
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] curMax = new int[nums.length];
int[] curMin = new int[nums.length];
int res = nums[0];
curMax[0] = nums[0];
curMin[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
curMax[i] = Math.max(Math.max(curMax[i - 1] * nums[i], nums[i]), curMin[i - 1] * nums[i]);
curMin[i] = Math.min(Math.min(curMax[i - 1] * nums[i], nums[i]), curMin[i - 1] * nums[i]);
if (curMax[i] > res) {
res = curMax[i];
}
}
return res;
}
int maxProduct(vector<int>& nums) {
if (nums.empty() || nums.size() == 0) {
return 0;
}
int res = nums[0];
int max_product = nums[0];
int min_product = nums[0];
for (int i = 1; i < nums.size(); i++) {
int cur_max = max(max(max_product * nums[i], nums[i]), min_product * nums[i]);
int cur_min = min(min(cur_max * nums[i], nums[i]), min_product * nums[i]);
if (cur_max > res) {
res = cur_max;
}
max_product = cur_max;
min_product = cur_min;
}
return res;
}
def maxProduct(nums):
if not nums or len(nums) == 0:
return 0
curMax = [0] * len(nums)
curMin = [0] * len(nums)
res = nums[0]
curMax[0] = nums[0]
curMin[0] = nums[0]
for i in range(1, len(nums)):
curMax[i] = max(max(curMax[i-1]*nums[i], nums[i]), curMin[i-1]*nums[i])
curMin[i] = min(min(curMax[i-1]*nums[i], nums[i]), curMin[i-1]*nums[i])
if curMax[i] > res:
res = curMax[i]
return res
4. 股票专题
在LeetCode中，有几个与股票相关的题目在面试中出现的频率也很高，这几个题有难有易，我们这里统一研究一下。
4.1. 买卖股票的最佳时机-低买高卖
LeetCode121 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择某一天买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
本题是最简单的一种情况，假设给定的数组为：[7, 1, 5, 3, 6, 4]。将其绘制成图表就是：
如果我们真的在买卖股票，我们肯定会想：一定要在最低点买，之后尽可能在最高点买。但是这里还有考虑时间和先后顺序，不能只考虑最大和最小点。在题目中，我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的，那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。 因此，我们只需要遍历价格数组一遍，记录历史最低点，然后每一天测试：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice) {
minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
def maxProfit(prices):
if not prices or len(prices) == 0:
return 0
min_price = float('inf')
max_profit = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_profit:
max_profit = price - min_price
return max_profit
int maxProfit(std::vector<int>& prices) {
int minprice = prices[0];
int maxprofit = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] < minprice) {
minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
4.2. 最多持有一支股票
LeetCode122，假如在121的题目要求上，在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。求最大利润。
示例1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
股票问题，核心原则就是低买高卖，对于本题，保底的分析是什么都不做，利润为0，但不会赔钱。如果想赚钱那就要低买高卖，同时只能先买后卖。 首先本题还是要找最高和最低点 ，但是不能单纯的搜索最大和最小值，因为要考虑时序，有一种简单的方法可以直接解决本题：由于交易次数不受限，累加所有上坡之和，即可获得最大利润。本质上这种方式就是贪心算法。
实现代码：
public int maxProfit(int[] prices) {
int answer = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
answer += prices[i] - prices[i - 1];
}
}
return answer;
}
int maxProfit(std::vector<int>& prices) {
int minprice = prices[0];
int maxprofit = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] < minprice) {
minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
def maxProfit(prices):
if not prices:
return 0
max_profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
max_profit += prices[i] - prices[i - 1]
return max_profit
拓展本题可以使用DP来做。 考虑到「不能同时参与多笔交易」，因此每天交易结束后只可能存在手里有一支股票或者没有股票的状态。 定义状态 dp[i][0] 表示第 i天交易完后手里没有股票的最大利润，dp[i][1]表示第 i 天交易完后手里持有一支股票的最大利润（i 从 0开始）。 考虑dp[i][0]的转移方程，如果这一天交易完后手里没有股票，那么可能的转移状态为前一天已经没有股票，即dp[i-1][0]，或者前一天结束的时候手里持有一支股票，即dp[i-1][1]，这时候我们要将其卖出，并获得 prices[i] 的收益。因此为了收益最大化，我们列出如下的转移方程： dp[i][0]=max{dp[i−1][0],dp[i−1][1]+prices[i]} 再来考虑dp[i][1]，按照同样的方式考虑转移状态，那么可能的转移状态为前一天已经持有一支股票，即 dp[i-1][1]，或者前一天结束时还没有股票，即dp[i-1][0]，这时候我们要将其买入，并减少 prices[i] 的收益。可以列出如下的转移方程： dp[i][1]=max{dp[i−1][1],dp[i−1][0]−prices[i]} 对于初始状态，根据状态定义我们可以知道第 0 天交易结束的时候dp[0][0]=0，dp[0][1]=−prices[0]。 因此，我们只要从前往后依次计算状态即可。由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候 dp[n-1][0] 的收益必然是大于dp[n-1][1]的，最后的答案即为dp[n-1][0]。
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < n; ++i) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[n - 1][0];
}
def maxProfit(prices):
n = len(prices)
dp = [[0, -prices[0]]]
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
return dp[n-1][0]
int maxProfit(std::vector<int>& prices) {
int n = prices.size();
if (n <= 1) {
return 0;
}
std::vector<int> dp(n, 0);
dp[0] = -prices[0];
for (int i = 1; i < n; ++i) {
dp[i] = std::max(dp[i - 1], dp[i - 1] + prices[i]);
dp[i] = std::max(dp[i], dp[i - 1] - prices[i]);
}
return dp[n - 1];
}
4.3. 买卖股票的最佳时机 III
LeetCode123.给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例1：
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第4天（股票价格=0）的时候买入，在第6天（股票价格=3）的时候卖出，这笔交易所能获得利润=3-0 = 3 。
随后,在第7天(股票价格=1)的时候买入,在第8天(股票价格=4)的时候卖出，这笔交易所能获得利润=4-1= 3 。
由于本题要求最多两次买卖，所以需要记录已经买卖了多少次。
第一步：确定状态
看序列的最后一步，在最优化策略中，最后一次卖发生在第j天，此时需要枚举最后一次买发生哪一天。 但是不知道之前是否买卖过。
如果不知道买卖过，就记录下来，我们知道此人买卖两次会经历过如下五个阶段：
如果这样的话 ，我们只要之前前一天的状态就能知道能否买卖股票。例如如果前一天在阶段5就不能买了，而如果在阶段四就可以决定是继续持有还是卖掉。 详细来看，如果要求前N天(第N-1天结束后)，在阶段5的最大获利，设为f[N][5],此时分两种情况： ●情况1：第N-2天就在阶段5——f[N][5]。 ●情况2：第N-2天还在阶段4（第二次持有股票），第N-1天卖掉。也就是f[n-1][4]+(P(n-1)-P(N-2))思考，为什么是这个？ 子问题就是求f[N-1][1]....f[N][5]。 如果要求前N天结束后，在阶段4获利最大，设为f[N][4]：
- 情况1：第N-2天就在阶段4—f[n-1][4]+(P(n-1)-P(N-2))
- 情况2：第N-2天还在阶段3—f[N-1][3]
- 情况3：第N-2天还在阶段2，第N-1天卖完了立即买—f[n-1][2]+(P(n-1)-P(N-2)
状态就是f[i][j]表示前i天(第i-1天)结束后，在阶段j的最大获利： 我们分两种情况看：如果昨天没有持有股票：
如果手中有股票：
到这里，我们顺便也将状态转移方程给确定了。 第三步：初始条件和边界情况 刚开始处于(第0天)处于阶段1，f[0][1]=0,f[0][2]=f[0][3]=f[0][4]=无穷 阶段1,3,5：f[i][j]=max{f[i-1][j],f[i-1][j-1]+P(i-1)-P(i-2)} 阶段2,4：f[i][j]=max{f[i-1][j]+P(i-1)-P(i-2),f[i-1][j-1],f[i-1][j-2]+P(i-1)-P(i-2)} 如果j-1<1或者j-2<1或i-2<0，对应项不计入max。 因为最多买卖两次，所以一定是清仓状态，也就是只能是max{f[N][1],f[N][3],f[N][5]}下才会获利最大。 第四步：按照顺序计算 计算顺序就是：初始化为f[0][1],...,f[0][5] 之后依次计算f[1][1],...,f[1][5] ... 一直到f[N][1],...,f[N][5]
public int maxProfit(int[] A) {
int n=A.length;
if(n==0){
return 0;
}
int [][]f=new int[n+1][5+1];
int i,j,k;
f[0][1]=0;
f[0][2]=f[0][3]=f[0][4]=f[0][5]=Integer.MIN_VALUE;
for(i=1;i<=n;i++){
for(j=1;j<=5;j+=2){
f[i][j]=f[i-1][j];
if(j>1&&i>1&&f[i-1][j-1]!=Integer.MIN_VALUE){
f[i][j]=Math.max(f[i][j],f[i-1][j-1]+A[i-1]-A[i-2]);
}
}
for(j=2;j<=5;j+=2){
f[i][j]=f[i-1][j-1];
if(i>1&&i>1&&f[i-1][j-1]!=Integer.MIN_VALUE){
f[i][j]=Math.max(f[i][j],f[i-1][j]+A[i-1]-A[i-2]);
}
if(j>2&&i>1&&f[i-1][j-2]!=Integer.MIN_VALUE){
f[i][j]=Math.max(f[i][j],f[i-1][j-2]+A[i-1]-A[i-2]);
}
}
}
return Math.max(Math.max(f[n][1],f[n][3]),f[n][5]);
}
int maxProfit(int A[], int n) {
if (n == 0) {
return 0;
}
int f[n+1][6];
int i, j, k;
f[0][1] = 0;
f[0][2] = f[0][3] = f[0][4] = f[0][5] = INT_MIN;
for (i = 1; i <= n; i++) {
for (j = 1; j <= 5; j += 2) {
f[i][j] = f[i-1][j];
if (j > 1 && i > 1 && f[i-1][j-1] != INT_MIN) {
f[i][j] = max(f[i][j], f[i-1][j-1] + A[i-1] - A[i-2]);
}
}
for (j = 2; j <= 5; j += 2) {
f[i][j] = f[i-1][j-1];
if (i > 1 && i > 1 && f[i-1][j-1] != INT_MIN) {
f[i][j] = max(f[i][j], f[i-1][j] + A[i-1] - A[i-2]);
}
if (j > 2 && i > 1 && f[i-1][j-2] != INT_MIN) {
f[i][j] = max(f[i][j], f[i-1][j-2] + A[i-1] - A[i-2]);
}
}
}
return max(max(f[n][1], f[n][3]), f[n][5]);
}
def maxProfit(A, n):
if n == 0:
return 0
f = [[0] * 6 for _ in range(n+1)]
f[0][1] = 0
f[0][2] = f[0][3] = f[0][4] = f[0][5] = float('-inf')
for i in range(1, n+1):
for j in range(1, 6):
if j % 2 == 1:
f[i][j] = max(f[i][j], f[i-1][j-1] + A[i-1] - A[i-2])
else:
f[i][j] = max(f[i][j], f[i-1][j] + A[i-1] - A[i-2])
if j > 2:
f[i][j] = max(f[i][j], f[i-1][j-2] + A[i-1] - A[i-2])
return max(max(f[n][1], f[n][3]), f[n][5])
5. 打家劫舍
LeetCode198.打家劫舍，你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12。
我们仍然按照DP的套路来分析本题。 第一步：确定状态和子问题 我们先看序列的最后一步：有可能偷或者不偷最后一栋房子N-1。 情况1：不偷房子N-1，简单，最优策略就是前N-1栋房子的最优策略。 情况2：偷房子N-1，仍然需要知道在前N-1房子中最多能偷多少金币，但是需要保证不偷第N-2栋房子。
那如何知道在不偷房子N-2的前提下，在前N-1栋房子中最多能偷多少金币呢？ ●用f[i][0]表示不偷房子i-1的前提下，前i栋房子中最多能偷多少金币。 ●用f[i][1]表示偷房子i-1的前提下，前i栋房子中最多能偷多少金币。上面两种情况用公式就是：如果不偷房子i-1就是：
如果偷房子i-1就是：
这个有两种情况 ，能否简化一下呢？在不偷房子i-1的前提下，前i栋房子中最多能偷多少金币其实就是前i栋房子最多能偷多少金币。因此公式就是： f[i]=max{f[i-1],f[i-2]+A[i-1]} 第二步：处理初始条件和边界情况 f[0]=0，没有房子，没的偷。 f[1]=A[0] f[2]=max{A[0],A[1]} 我们要的答案是f[n] 第三步：编程实现
public long houseRobber(int[] A) {
int n = A.length;
if (n == 0) return 0;
long[] dp = new long[n + 1];
dp[0] = 0;
dp[1] = A[0];
for (int i = 2; i <= n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + A[i - 1]);
}
return dp[n];
}
long houseRobber(vector<int>& A) {
int n = A.size();
if (n == 0) return 0;
vector<long> dp(n + 1, 0);
dp[0] = 0;
dp[1] = A[0];
for (int i = 2; i <= n; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + A[i - 1]);
}
return dp[n];
}
def houseRobber(A):
n = len(A)
if n == 0:
return 0
dp = [0] * (n + 1)
dp[0] = A[0]
for i in range(1, n + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + A[i - 1])
return dp[n]
6. 通关文牒
本文的重点是继续训练动态规划是如何解题的，只要理解，就算过关了。
