java - 了解简单动态规划的流程

Question

我刚刚开始理解动态规划的概念。我知道它用于缓存 future 调用的结果，并且它在设计提供指数运行时间的复杂算法方面非常有效。我不明白的是流程如何以编程方式工作。例如，使用动态规划计算第 n 个 Fibonacci 数，如下所示。程序中的流程是怎样的？

int[] fibMap = new int[max]
int fibo(int i){
  if(i == 0) return 0;
  if(i == 1) return 1;
  if( fibMap[i] != 0) return fibMap[i]; // return cached result
  fibMap[i] = fibo(i-1)+fibo(i-2);      //Cache result
  return fibMap[i];
}

我从我正在使用的一本 Java 引用书中找到了这段代码，但我很难弄清楚这个程序是如何工作的。假设我们想要计算一个简单的 fibo(3) 或 fibo(5)，有人可以向我解释程序如何缓存结果以及整体流程如何解决这个问题与没有 DP 的正常递归方法相比，如下所示？

int fibo(int i){
   if(i == 0) return 0;
   if( i == 1) return 1;
   return fibo(i-1) + fibo(i-2);
}

Answer 1

你的代码是

int fibo(int i){
  if(i == 0) return 0;
  if(i == 1) return 1;
  if( fibMap[i] != 0) return fibMap[i]; // return cached result
  fibMap[i] = fibo(i-1)+fibo(i-2);      //Cache result
  return fibMap[i];
}

或者，等价地

int fibo(int i){
  if(i == 0) return 0;
  if(i == 1) return 1;
  if( fibMap[i] == 0)
    fibMap[i] = fibo(i-1)+fibo(i-2);      //Cache result
  return fibMap[i];
}

因此“流”基本上与非缓存版本完全相同，除了您避免重新计算已经计算的结果。