動態規劃斐波那契數列

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]); 
     } 
    } 
}