一文了解分而治之和动态规则算法

这是我参与更文挑战的第18天，活动详情查看：更文挑战

众多周知，分而治之算法和动态规则算法是前端面试中的“宠儿”。而在我们的日常生活中，这两个场景的应用也相对比较广泛。比如，分而治之算法常用于翻转二叉树、快速搜索等场景中，而动态规则算法，则常用于最少硬币找零问题、背包问题等场景中。

在下面的这篇文章中，将讲解分而治之和动态规则的常用场景以及对 leetcode 的一些经典例题进行解析。

一、分而治之

1、分而治之是什么？

• 分而治之是算法设计中的一种方法。
• 它将一个问题分成多个和原问题相似的小问题，递归解决小问题再将结果合并以解决原来的问题。

2、应用场景

• 归并排序
• 快速搜索
• 二分搜索
• 翻转二叉树
• ……

3、场景剖析：归并排序和快速排序

（1）场景一：归并排序

• 分：把数组从中间一分为二。
• 解：递归地递归的对两个子数组进行归并排序。
• 合：合并有序子数组。

（2）场景二：快速排序

• 分：选基准，按照基准把数组分成两个子数组。
• 解：递归地对两个子数组进行快速排序。
• 合：对两个子数组进行合并。

二、动态规则

1、动态规则是什么？

• 动态规则是算法设计中的一种方法；
• 它将一个问题分解为相互重叠的子问题，通过反复求解子问题，来解决原来的问题。

看到这里，很多小伙伴会想着，动态规则和分而治之不是解决同样的问题吗？其实不是的。

注意：

• 动态规则解决相互重叠的子问题。

• 分而治之解决的是相互独立的子问题。

这样说可能还有点抽象，稍后将在第3点的时候做详细解析。

2、应用场景

• 最少硬币找零问题
• 背包问题
• 最长公共子序列
• 矩阵链相乘
• ……

3、场景剖析：斐波那契数列

斐波那契数列是一个很典型的数学问题。斐波那契数列指的是这样一个数列：

这个数列从第3项开始，每一项都等于前两项之和。即：