这是我在网上偶然发现的一些关于动态规划的讲座中读到的问题。(我已经毕业并且已经了解了动态规划的基础知识)
在解释为什么需要记忆化的部分,也就是说:
如果不使用记忆化,那么许多子问题将被重复计算多次,这使得复杂度非常高。
然后在一页上,笔记中有一个没有答案的问题,这正是我想问的。这里我使用确切的措辞和它所展示的例子:
在阅读本文之前,我甚至不知道有些编程语言内置了备忘录支持。笔记中的说法是否正确?如果是,那么为什么命令式语言不支持它呢?
在解释为什么需要记忆化的部分,也就是说:
// psuedo code
int F[100000] = {0};
int fibonacci(int x){
if(x <= 1) return x;
if(F[x]>0) return F[x];
return F[x] = fibonacci(x-1) + fibonacci(x-2);
}
如果不使用记忆化,那么许多子问题将被重复计算多次,这使得复杂度非常高。
然后在一页上,笔记中有一个没有答案的问题,这正是我想问的。这里我使用确切的措辞和它所展示的例子:
LISP示例说明它是有效的:自动记忆化:许多函数式编程语言(例如 Lisp)具有内置的记忆化支持。
为什么命令式语言(例如 Java)没有?
(defun F (n)
(if
(<= n 1)
n
(+ (F (- n 1)) (F (- n 2)))))
Java示例提供了指数级的解决方案
static int F(int n) {
if (n <= 1) return n;
else return F(n-1) + F(n-2);
}
在阅读本文之前,我甚至不知道有些编程语言内置了备忘录支持。笔记中的说法是否正确?如果是,那么为什么命令式语言不支持它呢?