加个“星标”，天天中午 12:15，一起学算法
这些问题大多在 上面标的都是 hard 难度，弄清楚了这些套路后，回过头去看看推导过程，然后再看看二、三十行的代码量，不知道是否能给你一些新的感悟和认识？
本文全长 1w 字，内容有点干，建议先收藏再阅读！
概论
前面我们说了和这两类动规题型，不知道你是否对动态规划有了更多的认识。
这里说一下，将动态规划分不同的题型来讨论主要为了更好地明确思路，往往不同类型的题目有着不同的切题点，当然你熟练了，题目做的多了，对动规思想理解透彻了，拿到一道题目马上能想到状态定义以及递推方程，那其实分不分题型没有任何差别，但是如果没有太多基础的，还是不太建议盲目做题动态规划，分题型来学习并总结效果可能会更好。
字符匹配类动态规划，你一听名字就知道和字符串匹配相关，这类题型它其实是 序列类动态规划 的一个递进，它有时也被称为 双序列类动态规划。
在 序列类动态规划 中，题目的输入是一个数组或是字符串，然后让你基于这个输入数组或是字符串进行一系列的判断，往往我们拆解问题、分析状态的时候只需要考虑一个维度的状态，比如刷房子和抢房子相关的问题，我们只需要考虑此时的房子和之前考虑过的房子之间的联系，思维始终是在一条线上。
回到字符匹配类动态规划，题目要你分析的是两个序列彼此之间的联系，这里其实有一个动态规划状态维度的提升，在考虑当前子问题的时候，我们要同时考虑两个序列的状态，当然，一般说来，动态规划状态维度的提升，也意味着难度的提升，可能刚从一维变成二维，你会不太习惯，没关系，多思考就好了，对于字符匹配类动态规划，它的题目特征其实特别明显，比如：
另外说一下，这类问题的难点在于问题的拆解上面，也就是如何找到当前问题和子问题的联系。
往往这类问题的状态比较好找，你可以先假设状态 dp[i][j] 就是子问题 str1(0...i) str2(0...j) 的状态。拆解问题主要思考 dp[i][j] 和子问题的状态 dp[i - 1][j]，dp[i - 1][j] 以及 dp[i - 1][j - 1] 的联系，因为字符串会存在空串的情况，所以动态规划状态数组往往会多开一格。
当然，对于这类问题，如果你还是没有什么思路或者想法，我给你的建议是 画表格，我们结合实际题目一起来看看。
题目分析
第 1143 号问题：最长公共子序列。
题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
示例 2:
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
示例 3:
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。
题目分析
让你求两个字符串的最长公共子序列，这道题目可谓是教科书般的经典，很多算法书籍都把这道题当作动态规划的思维范例进行讲解。
比如大名鼎鼎的 算法导论 ！！！
因此没做过的话，还是强烈建议去做一下。
这里还是按之前的四个步骤来思考，当然这只是一个框架用来辅助你思考，不用特别拘泥于这四个步骤：
参考代码
public int longestCommonSubsequence(String text1, String text2) {
int length1 = text1.length();
int length2 = text2.length();
int[][] dp = new int[length1 + 1][length2 + 1];
char[] textArr1 = text1.toCharArray();
char[] textArr2 = text2.toCharArray();
for (int i = 1; i <= length1; ++i) {
for (int j = 1; j <= length2; ++j) {
if (textArr1[i - 1] == textArr2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[length1][length2];
}
第 72 号问题：编辑距离。
题目描述
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2:
输入: word1 = "intention", word2 = "execution"
输出: 5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
题目分析
求解编辑距离，也是经典老题，编辑距离其实在实际工作中也会用到，主要用于分析两个单词的相似程度，两个单词的编辑距离越小证明两个单词的相似度越高。
题目说可以通过增加字符，删除字符，以及 替换字符 这三个操作来改变一个字符串，并且每个操作的 cost 都是 1，问一个单词转换成另一个单词的最小 cost，老样子，四个步骤分析一遍：
参考代码
public int minDistance(String word1, String word2) {
char[] arr1 = word1.toCharArray();
char[] arr2 = word2.toCharArray();
int[][] dp = new int[arr1.length + 1][arr2.length + 1];
dp[0][0] = 0;
for (int i = 1; i <= arr1.length; ++i) {
dp[i][0] = i;
}
for (int i = 1; i <= arr2.length; ++i) {
dp[0][i] = i;
}
for (int i = 1; i <= arr1.length; ++i) {
for (int j = 1; j <= arr2.length; ++j) {
if (arr1[i - 1] == arr2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j],
Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
}
}
return dp[arr1.length][arr2.length];
}
第 44 号问题：通配符匹配。
题目描述
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。
示例 3:
输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:
输入:
s = "acdcb"
p = "a*c?b"
输入: false
题目分析
题目给定两个字符串，一个字符串是匹配串，除了小写字母外，匹配串里面还包含 * 和 ? 这两个特殊字符，另一个是普通字符串，里面只包含小写字母。
题目问这个普通字符串是否和匹配字符串相匹配，匹配规则是 ? 可以匹配单个字符，* 可以匹配一个区间，也就是多个字符，当然也可以匹配 0 个字符，也就是空串。
依然是四个步骤走一遍：
参考代码
public boolean isMatch(String s, String p) {
char[] sArr = s.toCharArray();
char[] pArr = p.toCharArray();
boolean[][] dp = new boolean[pArr.length + 1][sArr.length + 1];
dp[0][0] = true;
for (int i = 1; i <= pArr.length; ++i) {
if (pArr[i - 1] != '*') {
break;
} else {
dp[i][0] = true;
}
}
for (int i = 1; i <= pArr.length; ++i) {
for (int j = 1; j <= sArr.length; ++j) {
if (sArr[j - 1] == pArr[i - 1] || pArr[i - 1] == '?') {
dp[i][j] = dp[i - 1][j - 1];
} else if (pArr[i - 1] == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
}
return dp[pArr.length][sArr.length];
}
第 97 号问题。
题目描述
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false
题目分析
题目的输入是三个字符串，问其中两个字符串是否能够交错合并组成第三个字符串，一个字符相对于其他字符的顺序在合并之后不能改变，这也是这道题的难点，不然的话你用一个哈希表就可以做了，三个字符串是否意味着要开三维的状态数组？还是四个步骤来看看：
参考代码：
public boolean isInterleave(String s1, String s2, String s3) {
int length1 = s1.length();
int length2 = s2.length();
int length3 = s3.length();
if (length1 + length2 != length3) {
return false;
}
boolean[][] dp = new boolean[length1 + 1][length2 + 1];
dp[0][0] = true;
char[] sArr1 = s1.toCharArray();
char[] sArr2 = s2.toCharArray();
char[] sArr3 = s3.toCharArray();
for (int i = 1; i <= length1; ++i) {
dp[i][0] = dp[i - 1][0] && sArr1[i - 1] == sArr3[i - 1];
}
for (int i = 1; i <= length2; ++i) {
dp[0][i] = dp[0][i - 1] && sArr2[i - 1] == sArr3[i - 1];
}
for (int i = 1; i <= length1; ++i) {
for (int j = 1; j <= length2; ++j) {
if (sArr3[i + j - 1] == sArr1[i - 1]) {
dp[i][j] |= dp[i - 1][j];
}
if (sArr3[i + j - 1] == sArr2[j - 1]) {
dp[i][j] |= dp[i][j - 1];
}
}
}
return dp[length1][length2];
}
总结
字符匹配类动态规划的问题还有挺多，比如 、 等等，这些问题都非常的经典，它们的难度都不低动态规划，但是这类问题其实是有套路的，首先状态特别好找，另外拆解问题也有一定的规律。
如果还是没有思路，那就画画表格吧，考虑当前格子的时候，看看其 左边，上边，左上边 这三个格子所代表的子问题的状态，有实际数据作为辅助，问题之间的递进关系相对来说会比较好找些。这些问题大多在 上面标的都是 hard 难度，弄清楚了这些套路后，回过头去看看推导过程，然后再看看二、三十行的代码量，不知道是否能给你一些新的感悟和认识？
-----------------------
限时特惠:本站持续每日更新海量各大内部创业课程，一年会员仅需要98元，全站资源免费下载
点击查看详情
站长微信:Jiucxh
