在计算机科学中,
动态规划是指将任何算法递归地分解为子问题,并在这个递归扩展中多次出现相同的子问题。一个简单的书例是,斐波那契数列可以使用动态规划来计算:
从通用递推式F(n) = F(n-1) + F(n-2)可以实现以下算法:
int fibonacci(n):
if (n < 2): return 1
else: return fibonacci(n-1) + fibonacci(n-2)
当然,这种方法并不高效,因为它会创建大量的递归调用,例如:
F(8) = F(7) + F(6) = [F(6) + F(5)] + [F(5) + F(4)] = ...
因此,我们已经看到这个实现中 fibonacci(5) 被计算了两次。现在采用“动态规划”范式来“记忆化”或“缓存”结果,如下所示:
integer_map store;
int memofibo(n):
if (n < 2) : return 1
else if (store.find_key(n)): return store.find_value(n)
else:
int f = memofibo(n-1) + memofibo(n-2)
store.set(n, f)
return f
这个实现确保对于每个参数值n,递归步骤最多执行一次,因此它可以在O(n log n)的时间内计算第n个斐波那契数(假设具有标准的O(log n)关联数组“store”实现)。
从计算机科学的角度来看,您提供的链接是相同思想的运筹学/优化问题版本,但这个想法已经在通用计算机科学领域中抽象成为递归+记忆化模式。希望这能帮助消除一些疑惑。