最近复习了下动规和贪心算法，借助 GPT 帮忙总结了下。
动态规划和贪心算法的区别#
总的来说，如果问题满足最优子结构和重叠子问题，那么可以考虑使用动态规划。如果问题满足最优子结构，以及可以通过局部最优解达到全局最优解（贪心选择性质），那么可以考虑使用贪心算法。如果问题同时满足上述所有特性，那么可能既可以使用动态规划，也可以使用贪心算法，具体选择哪种取决于实际问题的需求和限制。
- 子问题重叠
动态规划通常用于存在大量重叠子问题的情况。在动态规划中，一旦计算出一个子问题的解，就会将其存储起来，以便在再次需要计算该问题时直接使用。相反，贪心算法并不考虑子问题的重叠。 - 最优子结构
动态规划和贪心算法都需要问题具有最优子结构性质。这意味着可以通过子问题的最优解来得到原问题的最优解。 - 选择性质
贪心算法依赖于选择性质，即局部最优选择能导致全局最优解。贪心算法在每个决策阶段都会做出在当前看来是最好的选择，不考虑这个选择可能会对未来的决策产生什么后果。而动态规划则会评估所有可能的选项，并选择最优的一个。 - 解决问题的方式
贪心算法通常是一种迭代的方法，每一步都选择当前最优的解，而不需要考虑以前或者未来的决策。而动态规划通常需要创建一个表格来存储和查找所有的子问题解决方案。
如何判断一个问题是用动规还是贪心来解？#
- 确定问题是否是一个优化问题
例如最小路径问题，最大利润问题等，这些问题可能需要动态规划或贪心算法。 - 看是否存在 "最优子结构" 的特性
最优子结构意味着问题的最优解可以由其子问题的最优解构成。如果存在这样的结构，那么可能适合用动态规划或贪心算法解决。 - 对于动态规划，还要看问题是否有 "重叠子问题"
即是否存在多个问题共享同一子问题的情况，且重复计算会导致效率低下。这种情况常常适合用动态规划。 - 判断问题是否满足 "贪心选择性质"
即局部最优选择能导致全局最优解。也就是说，你可以一步一步地做出最优的选择，而不需要考虑整体。如果存在这样的特性，可能适合使用贪心算法。 - 需要考虑问题的复杂性和所需的解决速度
贪心算法通常更简单，计算速度也更快，但它并不总是能找到问题的最优解。相反，动态规划虽然可能更复杂，计算速度也可能较慢，但它更可能找到问题的最优解。 - 考虑问题的规模
对于大规模问题，动态规划可能需要大量的内存来存储子问题的解，这可能是不可行的。
如何拆解子问题？#
拆解子问题是解决动态规划和贪心算法问题的关键步骤。
记住，拆解子问题需要一些练习和经验。不同的问题可能需要不同的方法来拆解子问题，这需要时间和耐心来学习。
- 确定最优子结构
尝试找到一个更小的、简化的版本或子集的问题，这个子问题的解决方式应当与原问题相似。这种子问题的最优解会帮助我们构建原问题的最优解。 - 子问题的定义
你需要定义清楚子问题是什么。比如在最短路径问题中，子问题可能是从起点到达中间某个点的最短路径。 - 状态转移方程
这个方程表达了子问题之间是如何相互关联的。状态转移方程会告诉你如何从已经解决的子问题推导出当前子问题的解。 - 边界条件
找出最简单的子问题，它们的解是显而易见的。比如在斐波那契数列问题中，最初的两个数就是边界条件。 - 子问题之间的关系
在动态规划中，子问题通常会重叠，即某些子问题会在求解其他子问题时再次出现。这时就可以利用已经求解过的子问题的答案，避免重复计算。
5 个典型的动态规划问题#
-
- 斐波那契数列：给定 n，计算斐波那契数列的第 n 项。
-
- 钢条切割：给定一个长度和价格的列表，求出如何切割钢条可以得到最大的总价值。
-
- 最长公共子序列：给定两个字符串，找到最长的公共子序列。
-
- 0-1 背包问题：给定一组物品，每个物品都有自己的重量和价值，确定在不超过背包重量限制的情况下，如何选择物品以最大化总价值。
-
- 矩阵链乘法：给定一个矩阵链，我们需要决定最优的乘法顺序，以最小化总的乘法次数。
5 个典型的贪心算法问题#
-
- 活动选择问题：给定一组活动，每个活动都有开始时间和结束时间，我们需要选择最大数量的活动，使得这些活动之间没有时间上的冲突。
-
- 霍夫曼编码：用于数据压缩的一种算法，需要构建一个最优的霍夫曼树。
-
- Dijkstra 算法：用于求解图的单源最短路径问题。
-
- 分数背包问题：与 0-1 背包问题类似，但是物品可以被分割，我们需要决定如何选择和分割物品以最大化总价值。
-
- Kruskal 算法和 Prim 算法：用于求解图的最小生成树问题。