以最小的运行时间存储具有递归的Fibonacci序列的值

Question

我知道我的代码现在有很多问题,但我只是想在尝试任何事情之前弄清楚这些想法.我需要一个接受整数n的方法,该整数n返回Fibonacci序列中的第n个数字.虽然通过递归正常解决它,但我必须最小化运行时,所以当它得到类似于第45个整数的东西时,它仍然会相当快地运行.另外,我不能使用类常量和全局变量.

正常的方式w /递归.

public static int fibonacci(int n) {
    if (n <= 2) { // to indicate the first two elems in the sequence 
        return 1;
    } else { // goes back to very first integer to calculate (n-1) and (n+1) for (n)
        return fibonacci(n-1) + fibonacci(n-2); 
    }
}

我认为问题是这个过程中有很多冗余.我想我可以创建一个List来计算最多第n个元素,所以它只在我返回第n个元素之前运行一次.但是,在这种情况下,我很难看到如何使用递归.

如果我正确理解它,标准的递归方法很慢,因为有很多重复:

fib(6)= fib(5)+ fib(4)

fib(5)= fib(4)+ fib(3)

fib(4)= fib(3)+ 1

fib(3)= 1 + 1

这是接近这个的正确方法吗？是否需要使用某种形式的容器来获得更快的输出,同时仍然是递归的？我应该使用辅助方法吗？我刚刚进入递归编程,因为我已经习惯了迭代方法,所以很难解决这个问题.谢谢.

这是我有缺陷和未完成的代码:

public static int fasterFib(int n) {
    ArrayList<Integer> results = new ArrayList<Integer>();
    if (n <= 2) { // if 
        return 1;
    } else if (results.size() <= n){ // If the list has fewer elems than 
        results.add(0, 1);
        results.add(0, 1);
        results.add(results.get(results.size() - 1 + results.get(results.size() - 2)));
        return fasterFib(n); // not sure what to do with this yet
    } else if (results.size() == n) { // base case if reached elems
        return results.get(n);
    }
    return 0;
}

Answer 1

我想你想用一个Map<Integer, Integer>而不是一个List.您应该将该集合移到方法之外(因此它可以缓存结果) -

private static Map<Integer, Integer> results = new HashMap<>();

public static int fasterFib(int n) {
  if (n == 0) {
    return 0;
  } else if (n <= 2) { // if
    return 1;
  }
  if (results.get(n) != null) {
    return results.get(n);
  } else {
    int v = fasterFib(n - 1) + fasterFib(n - 2);
    results.put(n, v);
    return v;
  }
}

这项优化称为memoization,来自维基百科的文章 -

在计算中,memoization是一种优化技术,主要用于通过保持昂贵的函数调用的结果来加速计算机程序,并在再次发生相同的输入时返回缓存的结果.