509. Fibonacci Number

[문제 접근법]

- 피보나치 DP 메모이제이션을 활용하여 문제를 해결하였음

 

메모이제이션에 궁금하다면(그림으로 쉽게 설명되어있음)

https://namu.wiki/w/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

https://leetcode.com/problems/fibonacci-number/

Fibonacci Number - LeetCode

그림 1 - 피보나치 문제 설명

 

---

[구현1]

 - 제한사항에 (1<= n <= 30)이라 int[31]크기를 가진 배열을 선언하여 메모이제이션을 활용하였다.

static int dp[]=new int[31];

    public int fib(int n) {
        if(n <= 1) return n;
        if(dp[n] > 0)
            return dp[n];

        dp[n]=fib(n-2) + fib(n-1);

        return dp[n];
    }