프로그래머스 Lv2 멀리 뛰기

n = 1	{1}
n = 2	{2} {1, 1}
n = 3	{2, 1} {2, 1} {1, 1, 1}
n = 4	{2, 2} {2, 1, 1] {1, 2, 1} {1, 1, 2} {1, 1, 1, 1}

나는 이 문제를 점화식을 세워서 해결했다.

DP[n] = DP[n - 1] + DP[n -2]로 풀면 해결된다.

하지만,,, n = 0 일 때 1을 줘야하는 부분이 헷갈렸다. n = 2일 때를 생각하면 쉽게 풀리는 문제였다...

#include <string>
#include <vector>

using namespace std;

int DP[2001] = {};

long long solution(int n) 
{
    long long answer;
    DP[0] = 1;
    DP[1] = 1;
    
    for(int i = 2; i <= n; ++i)
    {
        DP[i] = (DP[i - 2] + DP[i - 1]) % 1234567;
    }
    answer = DP[n];
    return answer;
}