动态规划斐波那契数列

Question

我正在学习动态规划的斐波那契数列的应用程序，并有一个问题。下面是引用代码：

import java.math.BigInteger; 
import java.util.Arrays; 

public class FibonacciNumbersB { 

    static BigInteger[] dp = new BigInteger[10000]; 

    public static void main(String[] args) { 
     Arrays.fill(dp, BigInteger.ZERO); 
     dp[0] = BigInteger.ONE; 
     dp[1] = BigInteger.ONE; 

     for(int i = 4; i < 9999; i++) 
      System.out.println(fibRecurse(i).toString()); 
    } 

    public static BigInteger fibRecurse(int N) { 
     for(int i = 2; i < N; i++) { 
      // For numerous calls to this function, this will save as it goes 
      if(dp[i].equals(BigInteger.ZERO)) 
       dp[i] = dp[i - 1].add(dp[i - 2]); 
     } 

     return dp[N - 1]; 
    } 
} 

我有一份声明中检查，如果dp[i]在fibRecurse方法等于0（虽然fibRecurse不是递归）。

检查dp[i]已经计算好还是让dp[i]等于前两个元素的总和更有效率？

Answer 1

我宁愿Map<Integer, BigInteger>在执行此记忆化时使用固定BigInteger[]。请注意，您目前的做法是而不是递归。该Map可以声明和像

static Map<Integer, BigInteger> memo = new HashMap<>(); 
static { 
    memo.put(0, BigInteger.ONE); 
    memo.put(1, BigInteger.ONE); 
} 

初始化然后检查当前n出现在memo（如果是，返回它） - 否则，计算机和存储。像，

public static BigInteger fibRecurse(int n) { 
    if (memo.containsKey(n)) { 
     return memo.get(n); 
    } 
    BigInteger v = fibRecurse(n - 1).add(fibRecurse(n - 2)); 
    memo.put(n, v); 
    return v; 
} 

一个版本没有记忆化只会忽略memo像

public static BigInteger fibRecurseSlow(int n) { 
    if (n == 0 || n == 1) return BigInteger.ONE; 
    BigInteger v = fibRecurse(n - 1).add(fibRecurse(n - 2)); 
    return v; 
} 

我想你可以推断我所选择的方法名是慢。

Answer 2

import java.math.BigInteger; 
import java.util.Arrays; 

public class FibonacciNumbersB { 

    static BigInteger[] dp = new BigInteger[10000]; 

    public static void main(String[] args) { 
     dp[0] = BigInteger.ONE; 
     dp[1] = BigInteger.ONE; 
     int N = 9999; 
     fibRecurse(N); 
     for(int i = 0; i < N; i++) 
      System.out.println(dp[i].toString()) ; 
    } 

    public static void fibRecurse(int N) { 
     for(int i = 2; i < N; i++) { 

       dp[i] = dp[i - 1].add(dp[i - 2]); 
     } 
    } 
}