精选力扣300+题目之动态规划
# 字符匹配类动态规划心得总结
它的题目特征其实特别明显，比如：
- 输入是两个字符串，问是否通过一定的规则相匹配
- 输入是两个字符串，问两个字符串是否存在包含被包含的关系
- 输入是两个字符串，问一个字符串怎样通过一定规则转换成另一个字符串
- 输入是两个字符串，问它们的共有部分
这类问题的难点在于问题的拆解上面，也就是如何找到当前问题和子问题的联系。
往往这类问题的状态比较好找，你可以先假设状态 **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] 的联系，**因为字符串会存在空串的情况，所以动态规划状态数组往往会多开一格。
当然，对于这类问题，如果你还是没有什么思路或者想法，我给你的建议是 画表格，我们结合实际题目一起来看看。