动态编程与递归有多大不同
提问于 2020-09-30 07:09:43
我听说如果你能写一个递归代码，你就可以把它转换成一个动态编程代码，但是有什么必要这样做呢？以及如何将递归代码转换为DP？
回答 1
Stack Overflow用户
发布于 2020-09-30 11:02:47
在动态编程中有两种方法，自上而下和自下而上。
让我们以斐波那契数列为例：
f(0) =0:x= 1，
f(1) =1:x= 1，
f(x) = f(x-1) + f(x-2)：x>1
自上而下的方法：
它使用递归+记忆(存储计算的状态以避免重新计算)：
int memo[1000];//initialized by zeroes
int f(int x) {
if (x == 0 || x == 1) return 1;
if (memo[x] != 0) return memo[x]; //trying to avoid recalculation
memo[x] = f(x - 1) + f(x - 2); //storing the result
return memo[x];
}正如你在这里注意到的，为了计算f(x)的值，我们必须把它分解成f(x-1)和f(x-2)，这就是为什么它被称为自上而下。
自下而上的方法：
它使用循环(for，while...)而不是递归，并将值存储在数组中：
int memo[1000];
int bottom_up(int x) {
memo[0] = 1;
memo[1] = 1;
for (int i = 2; i < 1000; i++)
memo[i] = memo[i - 1] + memo[i - 2];
}正如你注意到的，我们计算斐波那契数列的值，从小到大，这就是为什么它被称为自下而上。
将代码从递归转换为循环被认为是将递归代码转换为迭代代码。
递归代码将多次调用自身，您应该知道每个函数调用都将存储在内存堆栈中，因此最好使用迭代方法，因为它对内存和性能更好。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/64132558
复制
腾讯云开发者
