在 R 中使用动态规划计算斐波那契

Question

我尝试编写一个函数来计算 R 中的第 n 个斐波那契数。我可以递归地执行此操作。

fibonacci = function(n){
  if (n == 1) {return(1)}
  if (n == 2) {return(2)}

  return(fibonacci(n - 1) + fibonacci(n - 2))
}

我在 R 中找不到任何示例，但是从其他语言的指南中我想出了以下内容。然而，它似乎并没有运行得更快。

fibonacci = function(n, lookup = NULL){
  if (is.null(lookup)) {
    lookup = integer(n + 1)
  }


  if (n == 1) {return(1)}
  if (n == 2) {return(2)}

  lookup[1] = 1
  lookup[2] = 2

  if (lookup[n - 1] == 0) {
    lookup[n - 1] = fibonacci(n - 1, lookup)
  }

  if (lookup[n - 2] == 0) {
    lookup[n - 2] = fibonacci(n - 2, lookup)
  }
  return(lookup[n - 1] + lookup[n - 2])
}

Answer 1

您的解决方案的问题在于，您的查找向量始终位于调用框架环境的本地，并且新的解决方案不会传播到调用者，即，当函数返回时，查找向量的更改会丢失。为了使持久变量成为 C 中的静态变量，您可以为充当存储器的函数创建一个属性。这是一种解决方案：

fibonaccid = function(n, init=T){
  if (init) {
    lookup <- integer(n + 1)
    lookup[1] <- 1
    lookup[2] <- 2
  } else {
    lookup <- attr(fibonaccid, ".lookup")
  }

  # ... calculate lookup as before, recurse with fibonaccid(...,init=F)

  attr(fibonaccid, ".lookup") <<- lookup

  return(lookup[n - 1] + lookup[n - 2])
}

这确实运行得更快：

R> system.time(print(fibonacci(35)))
[1] 14930352
   user  system elapsed
  20.923  0.140  21.446

R> system.time(print(fibonaccid(35)))
[1] 14930352
   user  system elapsed
  0.202   0.006   0.209

有关更多信息，请参阅此帖子。