贪心算法和动态规划以及分治法的区别？
贪心算法、动态规划和分治法是三种常见的问题求解策略，它们在解决问题时有着不同的特点和应用场景。
贪心算法：
贪心算法是一种在每一步选择中都采取当前状态下最优的选择，而不考虑全局最优解的算法。
它通常适用于一些具有最优子结构性质的问题，即局部最优解能导致全局最优解。
贪心算法通常比较简单，容易实现，但不能保证求得全局最优解，因为它对后续步骤的选择没有考虑。
适用于一些优化问题，例如最小生成树、最短路径等。
动态规划：
动态规划是一种通过将问题分解成子问题来求解的方法，通过存储子问题的解来避免重复计算，从而提高效率。
它适用于具有最优子结构性质和重叠子问题性质的问题。
动态规划通常通过填表格或者递推公式的方式求解，常见的例子有背包问题、最长公共子序列等。
动态规划求解的问题需要满足无后效性、最优子结构、重叠子问题等性质。
分治法：
分治法是一种将问题分解成若干个规模较小且相互独立的子问题，然后递归地求解子问题，最后合并子问题的解得到原问题的解的方法。
分治法适用于一些可分割为相似子问题的问题，例如归并排序、快速排序等。
分治法的基本思想是将原问题分解为互相独立的子问题，分别求解子问题，然后合并子问题的解得到原问题的解。
分治法通常通过递归实现，每一层递归都会将问题分解为规模更小的子问题，直到问题规模足够小可以直接求解。
总的来说，贪心算法是一种局部最优选择的算法，动态规划是一种利用子问题的解来求解原问题的方法，而分治法是一种将问题分解为相互独立子问题然后合并的方法。每种方法在不同的问题场景下有着各自的优劣势。
下面将分别用贪心算法、动态规划和分治法举例说明它们的应用：
贪心算法的例子：活动选择问题
在活动选择问题中，假设有一个需要使用同一资源的活动集合，每个活动都有一个开始时间和结束时间，只有一项资源可供使用。目标是找到最大的互不冲突的活动子集。
贪心算法的策略是每次选择结束时间最早的活动，这样可以给其他活动留下更多的空间。
例如，在课程安排中，每个课程有固定的开始时间和结束时间，通过贪心算法可以安排尽可能多的课程而不冲突。
动态规划的例子：最长递增子序列问题
给定一个序列，找出其中最长的递增子序列（不一定连续）的长度。
动态规划的思路是定义一个数组来存储以每个元素结尾的最长递增子序列的长度，然后利用状态转移方程来更新数组中的值。
例如，对于序列 [10, 22, 9, 33, 21, 50, 41, 60, 80]，最长递增子序列为 [10, 22, 33, 50, 60, 80]，长度为 6。
分治法的例子：归并排序
归并排序是一种经典的分治算法，它将待排序的序列分成两部分，分别对左右两部分进行排序，然后合并两个有序子序列。
通过递归地将序列划分为更小的子序列，直到无法再分，然后进行合并操作。
归并排序的时间复杂度为 O(nlogn)，其中 n 是序列的长度。
例如，对于序列 [38, 27, 43, 3, 9, 82, 10]，通过归并排序可以得到有序序列 [3, 9, 10, 27, 38, 43, 82]。
这些例子展示了贪心算法、动态规划和分治法在不同问题中的应用和特点。
贪心算法的例子：活动选择问题
想象一下，你有很多个游戏可以玩，但是它们的时间是有限的。每个游戏都有一个开始时间和结束时间。现在你想要尽可能多地玩游戏，但又不想让它们时间冲突，也就是说你想要挑选出尽可能多的不会同时进行的游戏。
那么贪心算法的思路就是这样的：每次你都选择最早结束的游戏来玩，这样就会给你留下更多的时间来玩其他游戏。这样做的话，你就能玩到最多的游戏，而且它们不会冲突。
动态规划的例子：最长递增子序列问题
假设你有一个有很多数字的列表，你想要找出这个列表中最长的递增的一串数字。递增的意思是越来越大，而且这串数字在原列表中不一定是连续的。
用动态规划的方法来解决这个问题，你可以这样想：我们可以用一个列表来记录每个数字结尾的最长递增序列的长度。然后，我们从头开始遍历原列表，对于每一个数字，我们都去看一下它前面的数字们，找出比它小的数字，然后看一下在它们中谁的递增序列最长，把它的长度加一就是当前数字结尾的最长递增序列长度。
分治法的例子：归并排序
归并排序就像是整理一副乱七八糟的扑克牌。假设你有一大堆乱糟糟的扑克牌，你想要把它们从小到大排列好。你可以这样做：先把牌分成两堆，然后分别把这两堆牌也排好序，最后把这两堆已经排好序的牌合并起来。
这就是分治法的思想：把一个大问题分成很多小问题，分别解决，然后把它们的解合并起来。最后，你就会得到整个问题的解决方案，就像你整理好了整副扑克牌一样。
动态规划的例子：最长递增子序列问题
假设我们有以下一串数字：
[10, 22, 9, 33, 21, 50, 41, 60, 80]
我们可以用动态规划来找出其中最长的递增子序列。
我们先创建一个列表来记录以每个数字结尾的最长递增子序列长度：
[1, 2, 1, 3, 2, 4, 4, 5, 6]
然后我们可以看到最长的递增子序列是 [10, 22, 33, 50, 60, 80]，它的长度是 6。
分治法的例子：归并排序
假设我们有一个乱序的数字列表：
[38, 27, 43, 3, 9, 82, 10]
我们可以用归并排序来将这个列表从小到大排序。
首先，我们把列表分成两半：[38, 27, 43, 3] 和 [9, 82, 10]。
然后，我们对每一半分别进行排序。分别得到 [3, 27, 38, 43] 和 [9, 10, 82]。
最后，我们将这两个有序的子列表合并起来得到最终的有序列表：[3, 9, 10, 27, 38, 43, 82]。
