数据结构第二季 Day18 动态规划中篇、最大连续子序列和、最长
2021-10-25 本文已影响0人
望穿秋水小作坊
一、动态规划中篇
1、动态规划的新手三步曲是什么？
- ①暴力递归（自顶向下，会出现重复计算子问题）
- ②记忆化搜索（自顶向下，为解决重复计算子问题）
- ③递推（自底向上，去除递归）
image.png
2、动态规划的常规步骤，也是三步曲（这应该是最重要的专业概念了）
- ①定义状态（状态是原问题、子问题的解）：比如定义 dp(i)的含义
- ②设置初始状态（边界）：比如设置 dp(0)的值
- ③确定状态转移方程：比如确定 dp(i) 和 dp(i-1) 的关系
- 上述概念结合
兑换零钱的例子，就理解起来很到位
image.png
image.png
3、可以通过动态规划来解决的问题，通常具备哪 2 个特点？分别是什么含义？
- 最优子结构（最优化原理）：通过求解子问题的最优解，可以获得原问题的最优解
- 无后效性：某阶段的状态一旦确定，则此后过程的演变不再受到此前各状态及决策的影响（未来与过去无关）
image.png
4、借助下面例子理解，什么是无后效性？
- dp(i-1) 对后面的 dp(i) 没有任何影响
image.png
5、结合例子理解，什么是有后效性？
- dp(i-1) 的路线选择，会对 dp(i)的结果造成影响，就是有后效性
image.png
二、最大连续子序列和
1、什么是最大连续子序列和的问题？
- 给定一个长度为 n 的整数序列，求它的最大连续子序列和？
- 比如 -2, 1, -3, 4, -1, 2, 1, -5, 4 的最大连续子序列和是 4 + (-1) + 2 + 1 = 6
2、它的状态如何定义？
- 状态定义真的很难，如果提高定义的效率呢？
- 总得来说还是得把题目读透彻了，如何把题目读透彻呢？
- 像下面的做法，把最优解获得的思路多分析几遍，看看有哪几种思路？
- 然后分析 i 从 0 到 8 的情况，大概率就能找到规律了。
- 总结：“走进题目，熟读题目”
image.png
3、状态定义好了，如何找状态转移方程和初始化？
image.png
4、有了动态规划的三要素，如何编写递推代码呢？
image.png
5、仔细观察上面的代码执行流程，是否存在优化点？
- 可以从以下两个角度入手找优化：
- ①分配了空间，但是后面都没用到了（从空间复杂度优化）
- ②能不能再循环的时候，顺便把事情做了（从时间复杂度优化）
- 分析上述代码：
- dp(6) 仅仅依赖于 dp(5)，dp(7)仅仅依赖于dp(6)，dp[i]仅仅依赖于 dp[i-1]
- 然而我们存了 dp[0]、dp[1]、dp[2]......dp(n) 的所有数据，所以我们的空间有点浪费的，是存在优化点的。
image.png
三、最长上升子序列
1、题意准确理解：子序列要求是连续的吗？
- 子序列不需要连续
2、什么是经典的：最长上升子序列问题？
image.png
- 拿到一道算法题，首先最重要的是理解题意
- 理解题意可以通过带入几个最优解的情况，这样比较容易深入理解题意。
2、动态规划 - 状态定义
image.png
3、动态规划 - 状态转换方程的定义
image.png
4、动态规划 - 代码的实现
image.png
5、使用牌堆和二分搜索法，是另一种思路（这种思路太难想，目前作为了解吧）
image.png
image.png
image.png
