动态规划的核心思想就是穷举求最值，步骤为：列出正确的「状态转移方程」，才能正确地穷举。判断算法问题是否具备「最优子结构」，是否能够通过子问题的最值得到原问题的最值。另外，动态规划问题存在「重叠子问题」，如果暴力穷举的话效率会很低，所以需要使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
如何列状态转移方程
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义
dp 数组/函数的含义。核心框架如下：
# 自顶向下递归的动态规划 def dp(状态1, 状态2, ...): for 选择 in 所有可能的选择: # 此时的状态已经因为做了选择而改变 result = 求最值(result, dp(状态1, 状态2, ...)) return result # 自底向上迭代的动态规划 # 初始化 base case dp[0][0][...] = base case # 进行状态转移 for 状态1 in 状态1的所有取值： for 状态2 in 状态2的所有取值： for ... dp[状态1][状态2][...] = 求最值(选择1，选择2...)