小编Mar*_*ott的帖子

我最近为了自己的娱乐而研究和测试各种Fibonacci算法,或多或少意外地提出了经典的O(n)时间和O(1)空间动态编程实现的替代实现.

考虑以下两个功能:

BigInt fib_dp_classic(int n) {
  if (n == 0) {
    return 0;
  }

  BigInt x = 0, y = 1, z;
  for (int i = 2; i <= n; ++i) {
    z = x + y;
    x = y;
    y = z;
  }

  return y;
}

和

BigInt fib_dp_mod(int n) {
  BigInt x = 0, y = 1, z = 1;
  for (int i = 0; i < n; ++i) {
    switch (i % 3) {
      case 0:
        y …