动态规划笔记

动态规划的流程：
暴力的递归解法->带备忘录的递归解法->迭代的动态规划

思考的过程：
找到状态和选择 -> 明确dp数组/函数的定义 ->寻找状态之间的关系

动态规划的一般形式：
求最值，最大最小值啊之类的。

动态规划的特点：
重叠子问题，具备「最优⼦结构」，「状态转移⽅程」

状态转移⽅程就是描述问题结构的数学形式：
例如：

你把 f(n) 想做⼀个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移⽽来，这就叫状态转移，仅此
⽽已。
如何写状态转移方程

• 需要确定状态，也就是原问题和⼦问题中变化的变量。
• 定义dp函数的定义 dp 的定义就是它代表什么
• 确定选择并择优 （选择可选的硬币中的一个）