分治算法与动态规划的区别

我假设你已经阅读了维基百科和其他关于这方面的学术资源，所以我不会重复使用任何信息。我还必须提醒，我不是计算机科学专家，但我将分享我对这些主题的理解……

动态规划

把问题分解成离散的子问题。Fibonacci序列的递归算法是动态规划的一个例子，因为它通过首先求解fib(n-1)来求解fib(n)。为了解决原来的问题，它解决了不同的问题。

分而治之

这些算法通常解决问题的相似部分，然后在最后将它们组合在一起。归并排序是分而治之的一个经典例子。这个例子和Fibonacci例子之间的主要区别是，在归并排序中，除法(理论上)可以是任意的，无论如何切片，仍然是归并和排序。要对数组进行归并排序，必须执行相同数量的工作，无论你如何划分它。求解fib(52)比求解fib(2)需要更多的步骤。

我认为Divide & Conquer是递归方法，Dynamic Programming是表填充。

例如，Merge Sort是一个Divide & Conquer算法，因为在每一步中，你将数组分成两部分，在这两部分上递归地调用Merge Sort，然后合并它们。

Knapsack是一个Dynamic Programming算法，因为你正在填充一个表，表示整个背包子问题的最优解。表中的每一项都对应于给定物品1-j的袋子中所能携带的最大重量w。

有时候在递归编程时，你会多次调用具有相同参数的函数，这是不必要的。

著名的斐波那契数列例子:

           index: 1,2,3,4,5,6...
Fibonacci number: 1,1,2,3,5,8...


function F(n) {
if (n < 3)
return 1
else
return F(n-1) + F(n-2)
}

我们运行F(5):

F(5) = F(4) + F(3)
= {F(3)+F(2)} + {F(2)+F(1)}
= {[F(2)+F(1)]+1} + {1+1}
= 1+1+1+1+1

动态编程方法:如果多次调用具有相同参数的函数，则将结果保存到变量中，以便下次直接访问。迭代方法:

if (n==1 || n==2)
return 1
else
f1=1, f2=1
for i=3 to n
f = f1 + f2
f1 = f2
f2 = f

我们再次调用F(5):

fibo1 = 1
fibo2 = 1
fibo3 = (fibo1 + fibo2) = 1 + 1 = 2
fibo4 = (fibo2 + fibo3) = 1 + 2 = 3
fibo5 = (fibo3 + fibo4) = 2 + 3 = 5

如您所见，每当您需要多重调用时，您只需访问相应的变量来获得值，而不是重新计算它。

顺便说一下，动态规划并不意味着将递归代码转换为迭代代码。如果需要递归代码，还可以将子结果保存到变量中。在这种情况下，这种技术被称为记忆。在我们的例子中，它是这样的:

// declare and initialize a dictionary
var dict = new Dictionary<int,int>();
for i=1 to n
dict[i] = -1


function F(n) {
if (n < 3)
return 1
else
{
if (dict[n] == -1)
dict[n] = F(n-1) + F(n-2)


return dict[n]
}
}

与分治法的关系是d&d算法依赖于递归。有些版本会出现“使用相同参数的多个函数调用问题”。在“矩阵链乘法”和“最长公共子序列”中搜索需要DP来改进D&D算法的T(n)的例子。

分而治之

分而治之的工作原理是将问题划分为子问题，递归地征服每个子问题，并将这些解决方案组合起来。

动态规划

动态规划是一种解决具有重叠子问题的问题的技术。每个子问题只解决一次，每个子问题的结果存储在一个表中(通常实现为数组或哈希表)，以供将来引用。这些子解可以用来获得原始解，存储子问题解的技术称为记忆。

你可能会想到DP = recursion + re-use

理解差异的一个经典例子是，这两种方法都可以获得第n个斐波那契数。检查来自麻省理工学院的材料。

分而治之的方法

动态规划方法

分而治之和动态规划的另一个区别是:

分而治之:

1. 在子问题上做更多的工作，因此有更多的时间消耗。
2. 分治法中子问题是相互独立的。

动态规划:

1. 只解决一次子问题，然后将其存储在表中。
2. 在动态规划中，子问题不是相互独立的。

动态规划与分治的相似之处

正如我现在看到的，我可以说动态规划是分而治之范式的扩展。

我不会把它们视为完全不同的东西。因为它们都是通过递归地将一个问题分解为两个或多个子问题来工作的具有相同或相关类型，直到它们变得足够简单，可以直接求解为止。然后将子问题的解组合起来给出原始问题的解。

那么为什么我们仍然有不同的范式名称，为什么我称动态规划为扩展。这是因为动态规划方法可以应用于问题只有当问题有一定的限制或先决条件时。在此之后，动态规划用记忆有关或制表技术扩展了分治方法。

让我们一步一步来……

动态规划先决条件/限制

正如我们刚刚发现的，为了使动态规划适用，分治问题必须具有两个关键属性:

• 最优子结构 -最优解可以由它的子问题的最优解构造

• 重叠子问题 -问题可以分解为多次重用的子问题，或者问题的递归算法可以一遍又一遍地解决相同的子问题，而不是总是生成新的子问题

一旦满足这两个条件，我们就可以说这个分治问题可以用动态规划方法来解决。

分而治之的动态规划扩展

动态规划方法通过两种技术(记忆有关和制表)扩展了分而治之的方法，这两种技术都具有存储和重用子问题解决方案的目的，可以极大地提高性能。例如，斐波那契函数的朴素递归实现的时间复杂度为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]
}

你可以阅读更多关于记忆和制表比较在这里。

这里您应该掌握的主要思想是，由于我们的分治问题具有重叠的子问题，因此可以缓存子问题的解决方案，从而实现记忆/制表。

那么到底DP和DC有什么区别呢

既然我们现在已经熟悉了DP的先决条件和它的方法，我们就可以把上面提到的所有内容放在一张图中了。

如果你想看代码示例，你可以看看这里有更详细的解释，在那里你会发现两个算法示例:二进制搜索和最小编辑距离(Levenshtein Distance)，它们说明了DP和DC之间的区别。

分而治之在每一级递归中涉及三个步骤:

1. 分问题的子问题。
2. 征服通过递归解决子问题。
3. 结合将子问题的解转化为原问题的解
   • 它是一个自顶向下方法
   它在子问题上做更多的工作，因此有更多的时间 李消费。< / > <李>。斐波那契数列的第n项可以用O(2^n)个时间复杂度计算。
   < br > 李< / ul > < / >

动态规划包含以下四个步骤 < br > 1。描述最优解的结构。 < br > 2。递归定义最优解的值。 < br > 3。计算最优解的值。
4. 构造一个最优解。

• 它是一个自底向上方法。
• 由于我们使用了之前计算的值，而不是再次计算，因此比分治算法花费的时间更少。
• 如。斐波那契数列的第n项可以用O(n)个时间复杂度来计算。< br > < br >

< >强为了便于理解，让我们将分而治之视为一种暴力解决方案，并将其优化视为动态规划。

注意:具有重叠子问题的分治算法只能用dp进行优化。

• 分而治之
  • 它们分解成互不重叠的子问题
  • 示例:阶乘数，即fact(n) = n*fact(n-1)

fact(5) = 5* fact(4) = 5 * (4 * fact(3))= 5 * 4 * (3 *fact(2))= 5 * 4 * 3 * 2 * (fact(1))

正如我们上面看到的，没有事实(x)是重复的，所以阶乘没有重叠的问题。

• < >强动态规划
  • 他们分成了重叠的子问题
  • 示例:斐波那契数列，即fib(n) = fib(n-1) + fib(n-2)

fib(5) = fib(4) + fib(3) = (fib(3)+fib(2)) + (fib(2)+fib(1))

如上所述，fib(4)和fib(3)都使用fib(2)。同样的，很多fib(x)被重复。这就是为什么斐波那契有重叠的子问题。

• 由于DP中子问题的重复，我们可以将这些结果保存在一个表中，节省了计算量。这被称为记忆有关

分而治之

• 此问题可通过以下三步解决: 1. 分 -划分为子问题的数量 2. 征服通过递归解决子问题来征服 3.Combine -结合子问题的解决方案得到原问题的解决方案
• 递归方法
• 自顶向下技术
• 例子:归并排序

动态规划

• 此问题的解决步骤如下: 定义最优解的结构 2.反复定义最优解的值。 以自底向上的方式获取最优解的值 4.从得到的值得到最终的最优解
• 非递归
• 自底向上技术
• 例子: Strassen的矩阵乘法

分而治之:

这一范式包括三个阶段:

1. 把这个问题分成更小的子问题
2. 征服，即解决这些较小的子问题
3. 结合这些子问题的解，得到最终答案。

动态规划:

DP是递归解的优化。它的主要区别在于它存储了子问题的解决方案，以后可以在查找其余子问题的解决方案的过程中访问这些解决方案。这样我们就不必每次都计算子问题的解决方案，而是可以简单地在计算机内存中查找它的值，假设它已经在之前得到了解决。我们可以简单地把它作为递归的基本情况。例如，我们正在通过递归解决一个问题，我们可以将子问题的解决方案存储在一个数组中，并通过在递归方法中的一个基本情况中添加相关代码来访问它们。

DP有两种实现方式:

考虑一个问题:求x的阶乘。

1. 制表法:我们使用自底向上的方法，也就是从最小的数一直到x，来找到解。

伪代码:

 1. int array
2. for int=1, i<=x, i++
3. array[i] = array[i-1]*i

2. 记忆法:我们使用自顶向下的方法，也就是说，我们把问题分解成更小的部分，然后解决它们，以得到最终的解决方案

伪代码:

 fac():
1. int array
2. if(x==0): return 1
3. if(array[x]!=null): return array[x]
4. return array[x] = x*fac(x-1)