动态规划

1.概念

动态规划常用于的一个问题就是求最值， 比如说最常见的求最长递增子序列啊等待。

其实动态规划的问题核心仍然是穷举，想一下求最值，那最可能的就是把所有结果列出来，谁最大要谁。

动态规划大部分是自底向上的，所以也就脱离了递归，更多的是采用for循环的迭代；

动态规划的典型类型：
背包问题；
打家劫舍；
股票问题；
子序列问题；

动态规划常常用于求解多阶段决策问题
动态规划问题的问法：只问最优解(常和最值联系在一起)，不问具体的解；

2.过程

动态规划类的题目我们一般情况下按照这三部曲进行：

• 1.确定dp数组及其下标含义；
• 2.确定递推公式，即状态转移方程；
• 3.dp初始化，base case；

一般按照这三步后能够写出来一个程序，为了保险起见，我们可以带一个例子进去检验。

最关键的就是确定好dp的含义后去寻找递推关系；

3.样例

509. 斐波那契数

70. 爬楼梯

746. 使用最小花费爬楼梯

121. 买卖股票的最佳时机

64. 最小路径和

198. 打家劫舍

213. 打家劫舍 II

5. 最长回文子串

120. 三角形最小路径和

4.体会

• 涉及到多决策的，之前想到的可能是用回溯，去构建一颗决策树；在不是平等的，比如说选1,2,3这样依次换着选一遍的情况时，我们很多情况下会去用动态规划，这和回溯的最大不同在于这里有一个很明确的递推关系，也就是状态转移，比如打家劫舍问题，或者是买卖股票等，dp数组在i时的状态能够由之前的递推出来；
• 很重要的一个点就是我们最初要明确好dp数组是干什么的，下标还有它本身的意义是什么。
• 要找到base case ，也就是把dp数组初始化好。