[Algorithm] Dynamic Programming

설명

• 이미 해결한 문제를 메모이제이션(Memoization) 처리하여 다시 풀지 않도록 하는 기법
• 피보나치 수열 문제가 대표적임
• 참고
  • https://m.blog.naver.com/ndb796/221233570962

코드

public class Solution {
    private static final Map<Long, Long> memo = new HashMap<>();

    public static long fibonacci(long x) {
        if (x <= 2) {
            return 1;
        }

        Long result = memo.get(x);

        if (result == null) {
            result = fibonacci(x - 1) + fibonacci(x - 2);
            memo.put(x, result);
        }

        return result;
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#x -> #result"() {
        expect:
        Solution.fibonacci(x) == result

        where:
        x  | result
        10 | 55
        50 | 12586269025
    }
}