数据结构与算法学习（三）：第三阶段知识总结

1. 动态规划概述

1. 概念

   • 一个模型（多阶段决策最优解模型）

     1. 解决问题的过程，需要经历多个决策阶段
     2. 每个决策阶段都对应着一组状态
     3. 寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值

   • 三个特征

     1. 最优子结构

        • 通过子问题的最优解，推导出问题的最优解

     2. 无后效性

        1. 在推导后面阶段的状态的时候，只关心前面阶段的状态值，不关心是怎么一步一步推导出来的
        2. 某阶段状态一旦确定，就不受之后阶段的决策影响

     3. 重复子问题

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

2. 特点

   1. 从最简单的问题开始，一点一点把问题复杂起来，在这个过程中寻找复杂问题是如何依赖简单问题的
   2. 需要记忆前面简单问题的解，然后用简单问题的解解决后面复杂问题的解

3. 和分治的区别

   1. 分治是自顶向下解决问题
   2. 动态规划是自底向上解决问题

4. 解题思路

   1. 状态转移表法：回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表-将填表过程翻译成代码
   2. 状态方程法：找最优子结构-写状态转移方程-将状态转移方程翻译成代码

2. 贪心算法概述

1. 概念

   • 每一步选择都采取当前状态下最有利的选择，从而希望结果是最优的

2. 应用

   1. 适用的场景比较有限，更多的是指导设计基础算法
   2. 经典应用有：霍夫曼编码、Prim 和 Kruskal 最小生成树算法、Dijkstra 单源最短路径算法

3. 解题步骤

   1. 当遇到问题的时候，首先要联想到贪心算法
   2. 尝试看这个问题是否可以用贪心算法解决
   3. 举几个例子看贪心算法产生的结果是否是最优的

3. 分治算法概述

1. 概念

   1. 将原问题划分成 n 个规模较小、结构与原问题相似的子问题
   2. 递归解决这些子问题，然后再合并其结果，得到原问题的解

2. 和递归的区别

   1. 分治算法是一种处理问题的思想
   2. 递归时一种编程技巧
   3. 分治算法一般都比较适合用递归来实现

3. 实现

   1. 分解：将原问题分解为一系列子问题
   2. 解决：递归求解各个子问题，若子问题足够小，则直接求解
   3. 合并：将子问题的结果合并成原问题

4. 应用条件

   1. 原问题与分解成的小问题具有相同的模式
   2. 原问题分解成的子问题可以独立求解，子问题之间没有相关性
   3. 具有分解终止条件
   4. 可以将子问题合并成原问题

4. 回溯算法概述

1. 概念

   1. 类似枚举搜索，枚举所有解，找到满足期望的解
   2. 把问题求解的过程分为多个阶段，每个阶段都会面对一个岔路口，先随意选一条路走
   3. 当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法

2. 实现

   • 递归

3. 和深度优先的区别

   1. 深度优先遍历的目的是“遍历”，本质是无序的
   2. 回溯的目的是“求解过程”，本质是有序的

4. 应用

   • 深度优先搜索
   • 八皇后
   • 0-1 背包
   • 图的着色
   • 旅行商问题
   • 数独
   • 全排列
   • 正则表达式匹配

5. 跳表概述

1. 概念

   • 链表加多级索引结构

2. 优点

   1. 支持快速插入、删除、查找操作，写起来不复杂，时间复杂度是 O(logn)
   2. 实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗
   3. 为了代码的简单、易读，会用跳表替代红黑树

6. 搜索概述

1. 图上的搜索算法

   • 在图中找出从一个顶点出发，到另一个顶点的路径

2. Dijkstra 算法

   • 概念

     1. 计算一个节点到其他所有节点的最短路径
     2. 一种单源最短路劲算法

   • 复杂度

     • 时间复杂度是 O(E*logV)

3. A* 算法

   • 和 Dijkstra 算法代码的 3 点区别
     1. 优先级队列构建的方式不同
     2. A* 算法在更新顶点 dist 值的时候，会同步更新 f 值
     3. 循环结束的条件不一样