인프런 커뮤니티 질문&답변

1. 현재 학습 진도

• 41강 4-8 DP 부분 수강 중입니다

   

   

2. 어려움을 겪는 부분

• 첨부해주신 Java 코드로 구현시 fib(100) 의 결과 값이 long 범위에 초과 되어 오버플로우가 발생하는 것 같습니다.

   

   

3. 시도해보신 내용

• BigInteger 를 도입하여 해결하긴 했지만, 더 나은 방법이 있다면 알려주시면 감사드리겠습니다. 

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class FiboDynamicProgramming {

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

    static {
        memo.put(1, BigInteger.ONE);
        memo.put(2, BigInteger.ONE);
    }

    // 1. 메모에 값이 있으면 반환
    // 2. 없으면 피보나치 공식 적용 및 메모이제이징
    private static BigInteger fiboDynamic(int n, Map<Integer, BigInteger> fiboMemo) {
        if (fiboMemo.containsKey(n)) {
            return fiboMemo.get(n);
        }

        BigInteger nthFibo = fiboDynamic(n - 1, fiboMemo).add(fiboDynamic(n - 2, fiboMemo)) ;
        fiboMemo.put(n, nthFibo);

        return nthFibo;
    }

    public static void main(String[] args) {
        System.out.println(fiboDynamic(100, memo));
    }

}