动态规划解题套路框架
动态规划三要素
-
重叠子问题：使用
备忘录来优化穷举过程，避免不必要的计算 -
最优子结构：通过
子问题的最值得到原问题的最值 -
状态转移方程
斐波那契数列
0和1开始，之后每一项都等于前两项之和： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
状态转移方程
\[f(n)= \begin{cases} 1, n=1或2\\ f(n-1)+f(n-2) \end{cases}\]凑零钱问题
给你 k 种面值的硬币，面值分别为 c1, c2 … ck ，每种硬币的数量无限，再给一个总金额 amount ，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。
最优子结构
因为硬币的数量是没有限制的，所以子问题之间没有相互制，是互相独立的。
状态转移方程
\[dp(n)= \begin{cases} 0, n=0\\ -1, n<0\\ min \lbrace dp(n - coin) + 1 | coin \in coins \rbrace, n>0 \end{cases}\]- base case： amount 为 0 时算法返回 0
- 状态：原问题和子问题中会变化的变量，即amount
- 选择：导致状态产生变化的行为，所有硬币的面值就是你的选择
- dp函数
- 自顶向下：递归函数
- 自底向上：数组迭代