算法设计

分治算法、贪心算法、回溯算法和动态规划等算法思想用于指导算法设计与实现。

分治算法

分治算法（Divide and conquer，也称分而治之）的核心思想是将原问题分解为多个规模较小且与原问题相似子问题，然后（递归地）求解这些子问题，再将子问题的解合并得到原问题的解。

分治算法是归并排序和快速排序等高级算法的基础。

贪心算法

贪心算法（Greedy algorithm，又称贪婪算法）的核心思想是在每一步做出当时看起来最佳选择，也就是总是做出局部最优选择，但并不保证总是能够找到全局最优解。

贪心算法通常用于求解具有贪心选择和最优子结构性质的问题。

• 贪心选择性质

总是做出当时看起来最优的选择，然后求解剩下的唯一子问题。

• 最优子结构性质

一个问题的最优解包含其子问题的最优解。

以下是贪心算法的主要应用场景：

• 霍夫曼编码

霍夫曼编码（Huffman coding）是一种数据压缩算法。

霍夫曼编码利用贪心算法来构造最优前缀码（所有字符编码都不会成为其他字符编码的前缀），贪心的将出现频率较高的字符使用较短的编码，反之使用较长的编码。

• Prim 和 Kruscal 最小生成树算法
• Dijkstra 单源最短路径算法

回溯算法

回溯算法（Backtracking）是一种搜索一个问题的所有期望解的方法。其核心思想是将问题的求解过程分为多个阶段，通过不断的试错来寻找期望解。在每个阶段求解问题的过程中，当它通过尝试发现，现阶段不能得到期望解时，它将回退到上一个阶段，继续尝试其它方法求解当前阶段的子问题，直到问题解决为止。

回溯法通常使用递归来实现，但是会出现一些重复子问题的情况，导致出现大量重复计算影响性能。不过，我们可以通过记忆化技术来避免重复计算问题。

剪枝技巧可以提前跳过一些无效分支，从而提高搜索效率。

以下是回溯算法的主要应用场景：

• 深度优先搜索算法
• 组合问题
• 排列问题
• 数独问题
• 八皇后问题

动态规划

动态规划（Dynamic programing，简称 DP）是一种通过将原问题分解为相对简单的子问题的方式来求解复杂问题的方法。

动态规划通常用于求解具有最优子结构和重复子问题性质的问题。

• 最优子结构性质

一个问题的最优解包含其子问题的最优解。这样，我们可以用子问题的最优解来构造原问题的最优解。

我们通常自底向上地使用最优子结构。首先求解子问题的最优解，然后选择能够得到原问题最优解的子问题，最后求原问题的最优解。

• 重复子问题性质

在用递归自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。我们对每个子问题只计算一次，然后将其结果存入状态表中，当再次遇到这个子问题时直接从状态表中取出并返回。

在使用动态规划求解问题时，我们需要定义状态和递推状态转移方程。

以下是动态规划的主要应用场景：

• 背包问题