什么题适合动态规划？
- 求最大值/最小值
- 判断是否可行
- 统计方案个数
什么题不适合动态规划？
- 求出所有具体方案而非方案的个数
- 输入数据是一个集合而不是序列
- 暴力算法的复杂度已经是多项式级别
- 动态规划擅长于优化指数级别复杂度（2^n, n!） -> 多项式级别复杂度（n^2, n^3）
- 不擅长优化 n^3 -> n^2
动规四要素
- 状态
- 灵感，创造力，存储小规模问题的结果
- 方程
- 状态之间的联系，怎么通过小的状态，来计算大的状态
- 初始化
- 最极限的小状态是什么，起点
- 答案
- 最大的那个状态是什么，终点
顺带回忆一下递归三要素
- 定义（状态）
- 接受什么参数
- 做了什么事
- 返回什么值
- 拆解（方程）
- 如何将参数变小
- 出口（初始化）
- 什么时候可以直接return
动态规划只能记录一种最优方案
练习题目：
https://leetcode.com/problems/triangle/description
https://leetcode.com/problems/minimum-path-sum/description
https://leetcode.com/problems/unique-paths/description
https://leetcode.com/problems/climbing-stairs/description
https://leetcode.com/problems/longest-increasing-subsequence/description
https://leetcode.com/problems/perfect-squares/description
https://leetcode.com/problems/largest-divisible-subset/description
https://leetcode.com/problems/russian-doll-envelopes/description