动态规划

一个模型三个特征

• 一个模型

  它指的是动态规划适合解决的问题的模型。我把这个模型定义为“多阶段决策最优解模型”。

  ​ 我们一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

• 三个特征

  • 最优子结构

    ​ 最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，==后面阶段的状态可以通过前面阶段的状态推导出来==。

  • 无后效性

    ​ 无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。

    ​ 第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

  • 重复子问题

    不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

动态规划解题思路

• 状态转移表

  一般能用动态规划解决的问题，都可以使用回溯算法的暴力搜索解决。

  ​ 所以，当我们拿到问题的时候，我们可以先用简单的回溯算法解决，然后定义状态，每个状态表示一个节点，然后对应画出递归树。从递归树中，我们很容易可以看出来，是否存在重复子问题，以及重复子问题是如何产生的。以此来寻找规律，看是否能用动态规划解决。

  • 解决重复子问题
    • 回溯+忘备录法
      • 就是将遍历的子问题保存下来，在遍历的时候先查询下，如果有了就直接拿来用。
      • 效率和动态规划差不多了。
    • 状态转移表法
      • dp数组，2维
      • dp数组，1维，滚动数组

• 状态转移方程

  状态转移方程是解决动态规划的关键

  • 写出状态转移方程
  • 根据状态转移方程，填充dp数组
  • 从dp数组中找到问题的解（一般来说最后一个是解）

如何实现搜索引擎中的拼写纠错功能？

程序实现参考代码随想录动态规划编辑距离

• 如何量化两个字符串的相似度？——==编辑距离==

  ​ 顾名思义，编辑距离指的就是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；相反，编辑距离就越小，说明两个字符串的相似程度越大。对于两个完全相同的字符串来说，编辑距离就是 0。

  • 莱文斯坦距离

    莱文斯坦距离允许增加、删除、替换字符这三个编辑操作。

    将两个字符串相互转换。

    莱文斯坦距离的大小，表示两个字符串差异的大小

  • 最长公共子序列

    最长公共子串的大小，表示两个字符串相似程度的大小。

    

• 纠错优化

  ​ 当用户在搜索框内，输入一个拼写错误的单词时，我们就拿这个单词跟词库中的单词一一进行比较，计算编辑距离，将编辑距离最小的单词，作为纠正之后的单词，提示给用户。

  • 针对纠错效果不好的问题，我们有很多种优化思路，我这里介绍几种。

    1. 我们并不仅仅取出编辑距离最小的那个单词，而是**取出编辑距离最小的 TOP 10，然后根据其他参数，决策选择哪个单词作为拼写纠错单词。**比如使用搜索热门程度来决定哪个单词作为拼写纠错单词。

    2. 我们还可以用多种编辑距离计算方法，比如今天讲到的两种，然后分别编辑距离最小的 TOP 10，然后求交集，用交集的结果，再继续优化处理。

    3. 我们还可以通过统计用户的搜索日志，**得到最常被拼错的单词列表，以及对应的拼写正确的单词。**搜索引擎在拼写纠错的时候，首先在这个最常被拼错单词列表中查找。如果一旦找到，直接返回对应的正确的单词。这样纠错的效果非常好。

    4. 我们还有更加高级一点的做法，引入个性化因素。针对每个用户，维护这个用户特有的搜索喜好，也就是常用的搜索关键词。当用户输入错误的单词的时候，我们首先在这个用户常用的搜索关键词中，计算编辑距离，查找编辑距离最小的单词。

  • 针对纠错性能方面，我们也有相应的优化方式。我讲两种分治的优化思路。

    1. 如果纠错功能的 TPS 不高，**我们可以部署多台机器，每台机器运行一个独立的纠错功能。**当有一个纠错请求的时候，我们通过负载均衡，分配到其中一台机器，来计算编辑距离，得到纠错单词。
    2. 如果纠错系统的响应时间太长，也就是，**每个纠错请求处理时间过长，我们可以将纠错的词库，分割到很多台机器。**当有一个纠错请求的时候，我们就将这个拼写错误的单词，同时发送到这多台机器，让多台机器并行处理，分别得到编辑距离最小的单词，然后再比对合并，最终决定出一个最优的纠错单词。

三种算法思想比较分析

贪心，回溯，动态规划

• 总结

  • 贪心：一条路走到黑，就一次机会，只能哪边看着顺眼走哪边
  • 回溯：一条路走到黑，无数次重来的机会，还怕我走不出来 (Snapshot View)
  • 动态规划：拥有上帝视角，手握无数平行宇宙的历史存档， 同时发展出无数个未来 (Versioned Archive View)

• 贪心

  ​ **贪心算法实际上是动态规划算法的一种特殊情况。**它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性（这里我们不怎么强调重复子问题）。

  **“贪心选择性”的意思是，通过局部最优的选择，能产生全局的最优选择。**每一个阶段，我们都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。

• 回溯

  ​ 回溯算法是个“万金油”。**基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。**回溯算法相当于==穷举搜索==。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。==对于大规模数据的问题，用回溯算法解决的执行效率就很低了。==

• 动态规划

  ​ 尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。==分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题==。