java - 使用java进行斐波那契数列修剪

Question

这是我使用 java 实现的斐波那契数列

/**
 * Returns nth fibonacci number
 */
public class fib {

   public static void main(String[] args){
      System.out.println(fibonacci(12));
   }

   public static int fibonacci(int n) {
      if (n == 0){
         return 0;
      } else if (n == 1){
         return 1;
      } else {
         return fibonacci(n - 1) + fibonacci(n - 2);
      }
   }
}

但是使用递归的这种方法的可视化让我认为它会快得多。这是 fib(5) 的可视化。 http://imgur.com/a/2Rgxs但这引起了我的思考，请注意底部，当我们从递归路径的底部向上冒泡时，我们计算 fib(2)、fib(3) 和 fib(4)，然后我们在最右上角重新计算 fib(3)分支。所以我在想，当我们冒泡备份时，为什么不保存从左分支计算的 fib(3)，这样我们就不会像我的方法当前所做的那样在右分支上进行任何计算，就像备份时的哈希表一样。我的问题是，我该如何实现这个想法？

Answer 1

当你想添加 HashMap 并保持原来的方法时，试试这个:

static HashMap<Integer, Integer> values = new HashMap<Integer, Integer>();

public static void main(String[] args){
    values.put(0, 0);
    values.put(1, 1);
    System.out.println(fibonacci(12));
}

public static int fibonacci(int n) {
    if (values.containsKey(n)){
        return values.get(n);
    } else {
        int left = values.containsKey(n - 1) ? values.get(n - 1) : fibonacci(n - 1);
        values.put(n - 1, left);
        int right = values.containsKey(n - 2) ? values.get(n - 2) : fibonacci(n - 2);
        values.put(n - 2, right);
        return left + right;
    }
}

如果您更频繁地调用它，这种方法可能会非常快，因为斐波那契结果已经存储在 values 中(当然这也可以通过其他方法完成):

public static void main(String[] args){
    values.put(0, 0);
    values.put(1, 1);
    System.out.println(fibonacci(12));
    System.out.println(fibonacci(11));
    System.out.println(fibonacci(10));
}