动态规划思路

拉勾教育版权所有：https://kaiwu.lagou.com/course/courseInfo.htm?courseId=3

动态规划思路

1.最优子结构
2.重复计算子机构
3.依靠递归，层层向上传值，所以编程时初始化子结构很重要

动态规划步骤

1.判断动态规划的类型

1.线性规划 >>> 一维数组
2.区间规划>>> 二维数组
3.约束规划 >>> 对输出结果有限制，并不是单纯的最优解

2.写出递归公式
3.编程实现

1.决定递推结果存储的数据结构，一般为数组
2.初始化
3.实现递推逻辑

##列子
1.线性规划
线性，就是说各个子问题的规模以线性的方式分布，并且子问题的最佳状态或结果可以存储在一维线性的数据结构里，例如一维数组，哈希表等。
解法中，经常会用dp[i]去表示第i个位置的结果，或者从0开始到第i个位置为止的最佳状态或结果。例如，最长上升子序列。dp[i]表示从数组第0个元素开始到第i个元素为止的最长的上.

#####题目
LeetCode第198题，给定一个数组，不能选择相邻的数，求如何选才能使总数最大。解法：这道题需要运用经典的0-1思想，简单说就是：“选还是不选”。

2.区间规划
区间规划，就是说各个子问题的规模由不同的区间来定义，一般子问题的最佳状态或结果存储在二维数组里。一般用 dp[i][j] 代表从第 i 个位置到第 j 个位置之间的最佳状态或结果。

#####题目
举例：LeetCode第516题，在一个字符串S中求最长的回文子序列。例如给定字符串为dccac，最长回文就是ccc。

对于回文来说，必须保证两头的字符都相同。用dp[i][j]表示从字符串第i个字符到第j个字符之间的最长回文，比较这段区间外的两个字符，如果发现它们相等，它们就肯定能构成新的最长回文。

当首尾的两个字符相等的时候 dp[0][n−1]=dp[1][n−2] + 2，

否则，dp[0][n−1]=max(dp[1][n−1], dp[0][n−2])。

3.约束规划
与前面不通的它计算的不是最优子结构，而是有条件的。
比如：0-1背包，它计算的不是背包最大的价值，怎么装东西才能最大化，而且还有一个重量的限定