什么是动态规划?
它与递归、记忆等有什么不同?
我读过维基百科上关于它的文章,但我还是不太明白。
什么是动态规划?
它与递归、记忆等有什么不同?
我读过维基百科上关于它的文章,但我还是不太明白。
当前回答
动态规划的关键是“重叠子问题”和“最优子结构”。问题的这些性质意味着最优解是由它的子问题的最优解组成的。例如,最短路径问题具有最优子结构。从A到C的最短路径是从A到某个节点B的最短路径,后面跟着从该节点B到C的最短路径。
更详细地说,要解决最短路径问题,您将:
求出从起始节点到触及它的每个节点的距离(比如从A到B和C) 求出这些节点到与其接触的节点的距离(从B到D和E,以及从C到E和F) 我们现在知道了从A到E的最短路径:它是我们访问过的某个节点x的A-x和x-E的最短和(B或C) 重复这个过程,直到到达最终的目标节点
因为我们是自下而上地工作,所以当需要使用这些子问题时,我们已经通过记忆它们得到了它们的解决方案。
记住,动态规划问题必须有重叠的子问题和最优的子结构。斐波那契数列的生成不是一个动态规划问题;它利用记忆,因为它有重叠的子问题,但它没有最优的子结构(因为不涉及优化问题)。
其他回答
记忆是指存储函数调用之前的结果(给定相同的输入,真正的函数总是返回相同的结果)。在存储结果之前,算法的复杂性并没有什么不同。
递归是函数调用自身的方法,通常使用较小的数据集。由于大多数递归函数可以转换为类似的迭代函数,这对算法复杂性也没有影响。
动态规划是解决较容易解决的子问题,并由此建立答案的过程。大多数DP算法将处于贪婪算法(如果存在的话)和指数算法(枚举所有可能性并找到最佳的一个)之间的运行时间。
DP算法可以用递归来实现,但它们不必这样做。 DP算法不能通过记忆来加速,因为每个子问题只被解决(或“solve”函数被调用)一次。
我对动态规划(一种针对特定类型问题的强大算法)也非常陌生。
简单地说,只需将动态规划视为使用前面知识的递归方法
以前的知识在这里是最重要的,跟踪你已经有的子问题的解决方案。
下面是来自维基百科的dp最基本的例子
求斐波那契数列
function fib(n) // naive implementation
if n <=1 return n
return fib(n − 1) + fib(n − 2)
让我们用n = 5来分解函数调用
fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
特别地,fib(2)从零开始计算了三次。在较大的示例中,需要重新计算fib(或子问题)的更多值,从而形成指数时间算法。
现在,让我们尝试将我们已经找到的值存储在一个数据结构(比如Map)中
var m := map(0 → 0, 1 → 1)
function fib(n)
if key n is not in map m
m[n] := fib(n − 1) + fib(n − 2)
return m[n]
这里我们将子问题的解决方案保存在地图中,如果我们还没有的话。这种我们已经计算过的保存值的技术被称为记忆化。
最后,对于一个问题,首先尝试找到状态(可能的子问题,并尝试考虑更好的递归方法,以便将以前的子问题的解决方案用于进一步的子问题)。
下面是一个简单的python代码示例,用于递归、自顶向下、自底向上的斐波那契数列:
递归:O (2 n)
def fib_recursive(n):
if n == 1 or n == 2:
return 1
else:
return fib_recursive(n-1) + fib_recursive(n-2)
print(fib_recursive(40))
自上而下:O(n)高效的大输入
def fib_memoize_or_top_down(n, mem):
if mem[n] is not 0:
return mem[n]
else:
mem[n] = fib_memoize_or_top_down(n-1, mem) + fib_memoize_or_top_down(n-2, mem)
return mem[n]
n = 40
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
print(fib_memoize_or_top_down(n, mem))
自底向上:O(n)为简单和小的输入大小
def fib_bottom_up(n):
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
if n == 1 or n == 2:
return 1
for i in range(3, n+1):
mem[i] = mem[i-1] + mem[i-2]
return mem[n]
print(fib_bottom_up(40))
动态规划
定义
动态规划(DP)是求解问题的一种通用算法设计技术 带有重叠子问题的问题。这项技术是美国人发明的 数学家理查德·贝尔曼在20世纪50年代。
关键理念
其关键思想是保存重叠的小问题的答案,以避免重新计算。
动态规划属性
使用较小实例的解决方案求解实例。 较小实例的解决方案可能需要多次使用, 所以把结果存储在一个表中。 因此,每个较小的实例只解决一次。 额外的空间被用来节省时间。
动态规划的关键是“重叠子问题”和“最优子结构”。问题的这些性质意味着最优解是由它的子问题的最优解组成的。例如,最短路径问题具有最优子结构。从A到C的最短路径是从A到某个节点B的最短路径,后面跟着从该节点B到C的最短路径。
更详细地说,要解决最短路径问题,您将:
求出从起始节点到触及它的每个节点的距离(比如从A到B和C) 求出这些节点到与其接触的节点的距离(从B到D和E,以及从C到E和F) 我们现在知道了从A到E的最短路径:它是我们访问过的某个节点x的A-x和x-E的最短和(B或C) 重复这个过程,直到到达最终的目标节点
因为我们是自下而上地工作,所以当需要使用这些子问题时,我们已经通过记忆它们得到了它们的解决方案。
记住,动态规划问题必须有重叠的子问题和最优的子结构。斐波那契数列的生成不是一个动态规划问题;它利用记忆,因为它有重叠的子问题,但它没有最优的子结构(因为不涉及优化问题)。