当前位置： 首页 >> 数据结构与算法 >> 动态规划

---

动态规划

2020-07-04 19:00:06 星期六  阅读：2296

---

####动态规划的特点 求解最优问题（最大最小值） 显著降低时间复杂度，时间复杂度为O(m* n)。时间复杂度比回溯算法低的原因是回溯算法实现存在大量的重复子问题。 空间换时间的思路 实际上是基于回溯算法演化而来的，就是为了解决回溯算法指数级别的时间复杂度而设计的。需要满足下面介绍的规则。 贪心算法实际上是动态规划算法的一种特殊情况。 尽管时间复杂度相对较低，但是并不是所有情况都适合用动态规划来求解。 ####经典的动态规划问题 背包问题升级版（不仅要重量最大，而且要价值最高） 购物车满减问题（比如满200减50，如何搭配购物车里的物品，可以最大限度的薅羊毛） ####几个算法的大白话对比 贪心：一条路走到黑，就一次机会，只能哪边看着顺眼走哪边 回溯：一条路走到黑，无数次重来的机会，还怕我走不出来 (Snapshot View) 动态规划：拥有上帝视角，手握无数平行宇宙的历史存档， 同时发展出无数个未来 一般能用动态规划解决的问题，都可以使用回溯算法的暴力搜索解决。使用回溯+备忘录的方式其实就可以解决性能问题了。 ####什么样的问题适合用动态规划来求解？ 可以概括为`一个模型三个特征` - 多阶段决策最优解模型 最优子结构：问题的最优解包含子问题的最优解。 无后效性：在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的 重复子问题：不同的决策序列，到达某个相同的阶段时，可能会产生重复状态。 ####动态规划解题思路总结 状态转移表法 - 回溯算法实现 定义状态 画递归树 找重复子问题 画状态转移表 根据递推关系填表 将填表过程翻译成代码 状态转移方程法 - 找最优子结构 写状态方程 将状态方程翻译成代码 ####动态规划实现搜索关键字纠错 比如Google搜索引擎，输入beajing，搜索引擎自动识别为beijing。 其原理是：当用户在搜索框内，输入一个拼写错误的单词时，我们就拿这个单词跟词库中的单词一一进行比较，计算编辑距离，将编辑距离最小的单词，作为纠正之后的单词，提示给用户。 量化两个字符串之间的相似度？ - 莱文斯坦距离：从A字符串通过增加、删除、替换字符变为B字符串的次数。两个字符串越相似，莱文斯距离越短； 最长公共子串长度：这个很好理解，就是两个字符串有多少字符是重合的。