动态规划算法
将问题分解为最优的子问题
递归的定义解通过子问题的最优解
optimal structure 最优子结构
一个问题可以分解为多个子问题,子问题有最优解,这个问题就可以通过子问题的最优解组合得出。
Overlapping subproblems 重叠子问题
边界
子问题可解
子问题独立
可以使用递归算法来解决。
在动态规划算法中使用数组来保存子问题的解,这样子问题多次求解的时候可以直接查表不用调用函数递归。
解决方法
Tabulation — bottom-up(自底向上)
Memoization — top-down(自上而下)
使用递归
- 本文作者: Kelly Liu
- 本文链接: http://tiantianliu2018.github.io/2019/08/12/Dynamic-Programming-动态规划/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!