动态规划 vs 回溯

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

什么是回溯法？

回溯法是一种问题解决技术。使用这种技术，我们可以解决我们的问题。这种策略使用暴力破解法，暴力破解法表示对于给定的问题，我们应该尝试所有可能的解决方案，并从所有可能的解决方案中选择所需的解决方案。相比之下，动态规划用于解决优化问题，但回溯法不用于解决优化问题。当给定问题存在多个解决方案时，回溯法会使用所有解决方案来解决问题。

现在我们将通过一个例子来理解动态规划如何使用暴力破解法。

假设有三名学生，两名女生，一名男生。我们有三把椅子，我们必须将这些学生安排在这些椅子上。我们有多少种方式可以安排这些学生？由于有 3 名学生，我们可以以 3！种方式安排这些学生，即 6 种方式。现在，我们必须找出所有可能的安排，所有这些安排或解决方案可以以树的形式表示，称为状态空间树。

G1、G2、B1

状态空间树

第一次安排

首先，考虑一个如下图所示的节点

考虑第一层中的第一个女孩 G1，即如下图所示的第一把椅子

考虑下一层中的第二个女孩 G2，即如下图所示的第二把椅子

考虑下一层中的一个男孩 B1，即如下图所示的第三把椅子

第二次安排

我们将回溯。首先，我们从第三把椅子上移除 B1，从第二把椅子上移除 G2。将 B1 添加到第二把椅子，然后将 G2 添加到第三把椅子，如下图所示

第三次安排

我们将再次回溯。首先，我们从第三把椅子上移除 G2，然后从第二把椅子上移除 B1，然后从第一把椅子上移除 G1。考虑第一把椅子上的 G2，如下图所示

考虑下一层中的 G1，即如下图所示的第二把椅子

考虑第三层中的 B1，即如下图所示的第三把椅子

第四次安排

我们将再次回溯。首先，我们从第三把椅子上移除 B1，然后从第二把椅子上移除 G1。将 B1 添加到第二把椅子，然后将 G1 添加到第三把椅子，如下图所示

第五次安排

我们将再次回溯。首先，我们从第三把椅子上移除 G1，然后从第二把椅子上移除 B1，然后从第一把椅子上移除 G2。

考虑第一层中的 B1，即如下图所示的第一把椅子

考虑下一层中的 G1，即如下图所示的第二把椅子

考虑下一层中的 G2，即如下图所示的第三把椅子

第六次安排

我们将再次回溯。首先，我们从第三把椅子上移除 G2，然后从第二把椅子上移除 G1。将 G2 添加到第二把椅子，然后将 G1 添加到第三把椅子，如下图所示

什么是动态规划？

动态规划是一种通过将复杂问题分解为更简单的子问题并精确地解决每个问题一次来高效解决某些类型复杂问题的技术。动态规划将子问题的结果存储在表中，并在需要时重新使用它们，以避免重复解决相同的问题。

哪些类型的问题可以使用动态规划解决？

以下是可以使用动态规划解决的两个问题

• 最优子结构：如果给定问题的最优解可以通过子问题的最优解获得，则给定问题具有最优子结构属性。换句话说，我们可以通过基于其子问题的递归关系来定义问题的解决方案。
• 重叠子问题：如果为了解决问题我们必须多次解决其子问题，则给定问题具有重叠子问题属性。

使用动态规划方法，我们避免解决重叠子问题，并且我们只解决每个问题一次并将结果保存在缓存中。当再次需要时，我们将从缓存中获取结果，而不是再次解决它们。

动态规划的方法

有两种方法用于实现动态规划

• 自上而下方法：它也称为记忆化。它使用递归和缓存实现。每当调用递归函数时，我们都会检查缓存以查看问题是否已解决。如果已解决，则我们从缓存中返回结果，否则我们将解决子问题，将结果保存到缓存中并返回结果。
• 自下而上方法：它也称为制表法。此技术用于首先解决所有较小的子问题，然后转向使用较小子问题结果的较大子问题。

动态规划与回溯法之间的区别

• 动态规划是将复杂问题分解为更简单的子问题的技术。此技术适用于具有以下属性的问题
  重叠子问题
  最优子结构
  回溯法是一种以增量方式递归构建解决方案，并随时删除所有不满足问题约束的解决方案的技术。
• 动态规划与回溯法的主要区别在于，动态规划完全依赖于最优性原理，这意味着序列的子序列应该是最优的。与动态规划相反，回溯法不保证完全最优解。
• 动态规划是一种解决优化问题的技术。优化问题使用最小值或最大值结果。与动态规划相反，回溯法使用暴力破解法，而不考虑优化问题。如果我们有多个解决方案，那么它会考虑所有这些解决方案。