문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

피보나치 수열(일반적으로 F(n)으로 표시)은 0과 1부터 시작하여 각 숫자가 앞의 두 숫자의 합인 피보나치 수열이라고 하는 수열을 형성한다.

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1

n이 주어졌을 때, F(n)을 구해라.

Example

#1
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1

#2
Input: n = 3
Output: 2
Explanantion: F(3) = F(2) + F(1) = 1 + 1 = 2

#3
Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3

Constraints

• 0 <= n <= 30

Solved

class Solution {
    public int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for(int i = 2; i < n + 1; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}