相关题目

https://leetcode-cn.com/problems/climbing-stairs/
https://leetcode-cn.com/problems/maximum-subarray/
https://leetcode-cn.com/problems/longest-increasing-subsequence/
https://leetcode-cn.com/problems/triangle/
https://leetcode-cn.com/problems/minimum-path-sum/

解题步骤

  1. 定义状态
  2. 总结状态转移方程
  3. 分析特殊情况
  4. 得到最终解
  5. 能不能继续优化

动态规划理论知识

“一个模型”：多阶段决策最优解模型
三个特征：最优子结构、无后效性和重复子问题。

最优子结构

最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。

无后效性

无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常 “宽松” 的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

重复子问题

不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。