数据结构学习笔记 - 动态规划

一时失言乱红尘 2022-09-02 05:19 159阅读 0赞

## 动态规划(Dynamic Programming) ##

动态规划比较适合求解最优问题, 比如最大值最小值, 可以非常显著的降低时间复杂度  
有点难, 求解过程不符合常规思维方式, 先看两个例子

### 0-1背包问题 ###

一组不同重量, 不可分割的物品, 选择一些装入背包, 在背包限重前提下, 背包里能装下的**物品重量最大值**  
回溯算法时间复杂度高, 指数级别, 回溯递归求解过程中, 有些子问题的求解是重复的, 此时可引入递归中的备忘录来解决, 避免冗余计算, 此时执行效率已经和动态规划差不多了  
而动态规划是这么做, 求解过程分为n个阶段, 每个阶段决策一个物品是否放到背包里  
每次决策后, 背包的重量会有多种情况, 会达到多种不同的状态, 我们把每一层重复的状态合并, 记录不同的状态, 就可以基于上一层状态集合, 推导下一层状态集合  
用一个二维数组记录, 横向是物品个数, 纵向是背包重量, 数组值是boolean类型, 根据物品重量依次填进去  
最后一层, 最接近末尾的数, 就是得到的解, 代码todo

动态规划解题思路, 把问题分解为多个阶段, 每个阶段对应一个决策, 记录每个阶段可达的状态集合, 通过当前阶段状态集合, 推导下一个阶段的状态集合, 动态地往前推进  
这也是动态规划名字的由来, 但需要额外申请一个n\* w+1的二维数组, 空间换时间, 可以优化到只用w+1的一位数组解决  
回溯算法时间复杂度O(2^n), 动态规划时间复杂度O(n\*w)物品个数乘可以承载总重量

### 0-1背包问题升级版 ###

一组不同重量, 不同价值, 不可分割的物品, 在满足背包最大重量限制前提下, 可装入的**总价值**最大是多少  
还是把求解过程分为n个阶段, 每个阶段决策一个物品是否放入背包, 每个阶段决策完后, 背包中的物品总重量及总价值会有多种情况  
用二维数组来记录每层可到达的不同状态, 横向物品个数, 纵向背包重量, 数组里存储的当前状态对应的最大总价值, 每层中重复的状态合并, 只记录价值最大的状态, 并基于此推导下一层状态  
时间复杂度和空间复杂度同上

### 动态规划解决的问题 ###

大部分动态规划能解决的问题, 都可以通过回溯算法来解决, 只不过回溯算法效率比较低  
什么样的问题适合用动态规划来解决, 一个模型三个特征  
动态规划适合解决的问题模型为 多阶段决策最优解模型  
我们一般是用动态规划来解决最优解问题, 而解决过程需要经历多个决策阶段, 每个阶段都对应一组状态,  
然后我们寻找一组决策序列, 经过这组决策序列, 能够产生最终期望求解的最优值  
三个特征, 最优子结构, 无后效性, 重复子问题  
最优子结构, 问题的最优解包含子问题的最优解, 可以通过子问题的最优解推导出问题的最优解, 即后面阶段的状态可以通过前面阶段的状态推导出来  
无后效性, 一是推导状态时, 只关心前面阶段的状态值, 不关心这个值怎么来的, 二是某个阶段状态一旦确定就不受后续决策影响  
重复子问题, 不同的决策序列, 到达某个相同的阶段时, 可能会产生重复的状态

### 动态规划解题思路 ###

动态规划解题的一般思路有两种, 状态转移表法和状态转移方程法

1.  状态转移表法  
    回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表-将填表过程翻译成代码  
    先画一个状态表, 一般是二维的, 用二维数组, 每个状态包含三个变量, 行列和数组值, 我们根据决策的先后过程, 从前往后填充状态表中的每个状态  
    并将递推填表的过程, 翻译成代码, 就是动态规划代码了  
    如果问题的状态比较复杂, 需要很多变量来表示, 那对应的状态表就需要是高维的, 就不适合用状态转移表法来解决了
2.  状态转移方程法  
    找最优子结构-写状态转移方程-将状态转移方程翻译成代码  
    有点类似递归的解题思路, 需要分析某个问题如何通过子问题来递归求解, 也就是所谓的最优子结构, 根据最优子结构写出递归公式, 也就是所谓的状态转移方程  
    两种代码实现方法, 一种是递归加备忘录, 一种是迭代递推  
    状态转移方程是解决动态规划的关键  
    有的问题适合用第一种思路, 有的问题适合用第二种思路, 需要结合题目分析

### 四种算法思想比较分析 ###

贪心, 回溯, 动态规划可以归为一类, 解决问题的模型都可以抽象成多阶段决策最优解模型, 而分治算法不行  
回溯算法是个万金油, 基本上能用动态规划和贪心解决的问题, 都可以用回溯算法, 不过时间复杂度非常高, 只能用来解决小规模数据问题  
动态规划高效但不能解决所有问题, 需要满足三个特征  
贪心算法实际上是动态规划的一种特殊情况, 解决问题更高效, 代码也更简洁, 能解决的问题也更有限, 需要满足三个条件, 最优子结构, 无后效性和贪心选择性  
(通过局部最优的选择能产生全局最优选择)  
拿到问题先不思考计算机如何实现, 单纯考虑人脑会如何去解决, 然后总结规律, 再套用学过的算法

### 拓展-拼写纠错 ###

拼写纠错功能, 量化两个字符串的相似度, 需要用到非常著名的量化方法, 编辑距离  
编辑距离指, 将一个字符串转化成另一个字符串, 需要的最少编辑操作次数, 比如增加/删除/替换一个字符, 编辑距离越大, 说明两个字符串相似度越小,  
两个完全相同的字符串, 编辑距离是0  
根据所包含的编辑操作种类不同, 编辑距离有多种不同的计算方式, 比较著名的有莱文斯坦距离(todo)和最长公共子串长度(todo)  
莱文斯坦距离允许增加, 删除, 替换字符三个编辑操作, 最长公共子串长度只允许增加, 删除两个编辑操作  
莱文斯坦距离表示两个字符串差异的大小, 最长公共子串的大小表示两个字符串相似程度的大小  
具体细节略