动态规划.md

动态规划特点：

1. 重叠子问题
2. 状态转移方程
3. 最优子结构

题型：求最值 核心：穷举

解题套路：

1. 明确[状态]
2. 明确[选择]
3. 明确 dp 函数、数组的定义
4. 明确 base case

代码框架

// 初始化代码框架
dp[0][0][...] = base
// 进行状态转移
for 状态1 in 状态1的所有取值：
   for 状态2 in 状态2的所有取值：
     for……
       dp[状态1][状态2][...] = 求最值(选择1,选择2...)

示例

• 最小编辑距离
• 最长回文子串