动态规划与分而治之比较

• 刻画一个最优解的结构特征。
• 递归地定义最优值。
• 自底向上地计算最优值，通常使用表格来存储中间结果。
• 根据计算得到的最优值构造一个最优解。

• 背包问题、最短路径问题（如Dijkstra算法）、最长公共子序列问题等。

分而治之（Divide and Conquer）：

1. 特点：
   • 分而治之将一个大问题分解成小的、相互独立的子问题，并递归地解决这些子问题。
   • 子问题的解决结果通过合并操作得到原问题的解。
   • 通常用于可以将问题划分为相互独立的子问题的情况。

• 将原问题划分为若干个规模较小且相互独立的子问题。
• 递归地解决这些子问题。
• 将子问题的解合并起来，得到原问题的解。

• 快速排序、归并排序、二分查找等。

区别：

• 重复子问题：
  
  • 动态规划关注的是重叠子问题，通过记忆化或表格来存储并重复使用已经解决过的子问题。
  • 分而治之通常是将问题分割成独立的子问题，不一定存在重叠子问题。
• 最优子结构：
  
  • 动态规划问题通常具有最优子结构，即全局最优解可以通过子问题的最优解得到。
  • 分而治之的问题不一定具有最优子结构，它只要求问题可以被分割成相互独立的子问题。
• 应用场景：
  
  • 动态规划通常用于求解最优解问题，例如优化问题。
  • 分而治之通常用于求解可以独立解决的子问题的问题。
• 时间复杂度：
  
  • 动态规划可能通过存储中间结果而降低时间复杂度。
  • 分而治之通常不涉及存储中间结果，而是递归地解决子问题。

动态规划和分而治之的相似之处
动态规划是分而治之范式的扩展。

• 因为它们都通过递归地将问题分解为两个或多个相同或相关类型的子问题来工作，直到这些问题变得足够简单可以直接解决。
• 然后将子问题的解决方案组合起来以给出原始问题的解决方案。

那么为什么我们仍然有不同的范式名称？
这是因为：

• 只有当问题具有一定的限制或先决条件时（上下文），动态规划方法才可以应用于该问题。
• 之后，动态规划通过记忆或制表技术扩展了分而治之的方法。

上文限制：
为了使动态规划适用，分而治之的问题必须具备两个关键属性：一旦满足这两个条件，我们就可以说这个分而治之的问题可以使用动态规划方法来解决。

分而治之的动态编程扩展动态编程方法通过两种技术（记忆和制表）扩展了分而治之的方法，这两种技术都具有存储和重用子问题解决方案的目的，从而可以极大地提高性能。

例如，Fibonacci 函数的简单递归实现的时间复杂度为 O(2^n)，而 DP 解决方案只需 O(n) 时间即可完成相同的操作。记忆化（自上而下的缓存填充）是指缓存和重用先前计算结果的技术。

因此，缓存的 fib 函数将如下所示：

memFib(n) {
    if (mem[n] is undefined)
        if (n < 2) result = n
        else result = memFib(n-2) + memFib(n-1)
        mem[n] = result
    return mem[n]
}

制表（自下而上的缓存填充）与此类似，但重点是填充缓存的条目。计算缓存中的值最简单的方法是迭代。fib 的制表版本如下所示：

tabFib(n) {
    mem[0] = 0
    mem[1] = 1
    for i = 2...n
        mem[i] = mem[i-2] + mem[i-1]
    return mem[n]
}

分而治之实例：二进制搜索
二进制搜索算法又称半区间搜索，是一种在排序数组中查找目标值位置的搜索算法。二进制搜索将目标值与数组的中间元素进行比较；如果两者不相等，则去掉目标值不在其中的那一半，继续搜索剩下的一半，直到找到目标值。如果搜索结束时剩余的一半为空，则说明目标值不在数组中。

在这里，你可以清楚地看到解决问题的分而治之原则。我们正在反复将原始数组分解为子数组，并试图在其中找到所需的元素。
我们能应用动态编程吗？不能，因为没有重叠的子问题。每次我们都将数组分割成完全独立的部分。而根据 "分而治之 "的先决条件/限制，子问题必须以某种方式重叠。

每次我们将数组分割成完全独立的部分。根据分而治之的先决条件/限制，子问题必须以某种方式重叠。

通常，每次绘制决策树并且它实际上是一棵树（而不是决策图）时，这意味着您没有重叠的子问题，这不是动态规划问题。

代码在这里您可以找到二分搜索功能的完整源代码以及测试用例和解释。

动态编程示例：最小编辑距离
通常，当涉及动态规划编程示例时，默认采用斐波那契数算法。

但是，让我们采用更复杂一点的算法来获得某种变化，以帮助我们理解这个概念。
最小编辑距离（或编辑距离）是用于测量两个序列之间差异的字符串度量。非正式地，两个单词之间的编辑距离是将一个单词更改为另一个单词所需的单字符编辑（插入、删除或替换）的最小数量。

例如“kitten”和“sitting”之间的编辑距离为 3，因为将一个更改为另一个没有办法用少于三个编辑来完成此操作。
这具有广泛的应用，例如拼写检查器、光学字符识别的校正系统、模糊字符串搜索以及基于翻译记忆库辅助自然语言翻译的软件。

在这里您可以找到最小编辑距离函数的完整源代码以及测试用例和解释。