• 复杂度来源:

  • 状态有更多维度（二维，三维，...可能需要压缩）

  • 状态转移方程更加复杂

• 常见题型:

使用最小花费爬楼梯
解码方法
最长有效括号
最大矩形
不同的子序列

• 不同路径II DP方程:

	for r in 1..<rows {
	
   		for c in 1..<cols where obstacleGrid[r][c] == 0 {
   		
       		dp[r][c] = dp[r-1][c] + dp[r][c-1]
		}
	}
	

• 常见题目分类：

  • 基础问题： 转化大小写，转换整型，等等
  • 操作问题： 判断前缀，翻转字母，等等
  • 异位词问题： 哈希思想
  • 回文串问题： 双指针
  • 最长子串 / 子序列问题： 结合DP
  • 字符串 + DP问题

• 字符串匹配算法

  • 暴力
  • Rabin - Karp 算法
  • KMP 算法

• 常见题型:
  见本周作业字符串相关题目