动态规划 vs 分治法

在了解动态规划与分治法之间的区别之前，我们应该分别了解动态规划和分治法。

什么是分治法？

分治法是一种用于解决问题的策略。策略可以定义为解决问题的途径。为了解决计算问题，这种策略已经被设计出来。有各种可用的技术来解决问题，但我们必须决定该技术是否适合该问题。

假设问题很大，那么我们就将问题分解成更小的子问题，然后单独解决这些子问题。一旦所有子问题都得到解决，我们就将所有子问题的解合并起来，以找到大问题的解。如果子问题也很大，那么就再次应用分治策略来解决子问题。分治策略的约束是子问题应该与主要问题相同。假设主要问题是排序，那么子问题也应该是排序。分治策略本质上是递归的。如果问题很大，我们就递归地解决该问题。

分治法的通用方法

由于动态规划是递归的，所以过程是递归的，算法也是递归的。

以下是可以使用分治策略解决的问题

• 归并排序：将数组分成两半，递归地对左半部分和右半部分进行排序，然后合并这两半。这种技术被称为归并排序。
• 快速排序：首先，将数组划分为小项和大项，然后递归地对这两组进行排序。这种技术被称为快速排序。

分治法的示例

• 搜索：分治法策略用于二分查找。
• 排序：归并排序和快速排序是分治技术的一个例子。
• 树的遍历
• 矩阵乘法

什么是动态规划？

动态规划意味着将优化问题分解成更简单的子问题，并存储每个子问题的解，以便每个子问题可以被解决一次。一旦所有子问题都得到解决，我们就将每个子问题的结果连接起来，以找到初始问题的解。

每个动态规划都有四个步骤

• 动态规划的执行方式是使问题能够分解成最优子问题。
• 它通过将解表示为更小子问题的最优解来递归地定义解的值。
• 我们将计算最优解的值。
• 根据计算出的值构建最优解。

让我们以表格形式理解每个步骤。

以下问题可以使用动态规划解决

• 最优子结构：问题的最优解包含所有子问题的最优解。
• 重叠子问题：递归解包含大量重复出现的简单子问题。

动态规划技术

有两种解决问题的方法

• 自下而上方法： 假设我想成为一名出色的程序员。首先，我会练习，然后参加比赛。我会多练习并努力提高。经过努力，我将成为一名出色的程序员。这是自下而上的一种方法。
• 自顶向下方法： 这种方法与自下而上方法相反。我将从最终解决方案开始。首先，我将成为一名出色的程序员。然后，我会多练习并努力提高。我将参加比赛，然后我会进行练习。

分治法与动态规划的区别