进阶算法—动态规划基础篇

什么是动态规划

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

动态规划的解题步骤

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

基础题目

509. 斐波那契数

思路

斐波那契数

70. 爬楼梯

思路

爬楼梯

746. 使用最小花费爬楼梯

思路

746. 使用最小花费爬楼梯

62. 不同路径

思路

62. 不同路径

63. 不同路径 II

思路

63. 不同路径 II

343. 整数拆分

思路

343. 整数拆分

96. 不同的二叉搜索树

思路

96. 不同的二叉搜索树