동적 프로그래밍 피보나치 시퀀스

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

(fibRecurse 재귀 아니지만) dp[i]가 fibRecurse 방법 0 동일한 경우 나는 문 체크가 : 여기에 참조 할 수 있도록 코드입니다.

dp[i]이 이미 계산되었는지 확인하거나 dp[i]을 이전 두 요소의 합계와 같게하는 것이 더 효율적입니까?

Answer 1

나는이 메모이 제이션을 수행 할 때 고정 BigInteger[]를 사용을 통해 Map<Integer, BigInteger>을 선호 할 것입니다. 현재 접근 방식은 이 아니며재귀이 아닙니다. 그렇지 않으면, 컴퓨터 및 보관 - Map는 그런 다음 현재 n가 (이 경우, 반환)을 memo에있는 경우 확인 선언

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

처럼 초기화 될 수 있습니다. 난 당신이 느린 내가 선택한 방법 이름에서을 추론 할 수 있다고 생각 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; 
} 

추천하기 추천,

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

버전

메모이 제이션 없이 단순히 생략 할 것이다.

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