class Solution {
public int solution(int n) {
int answer = 0;
// DFS 같은데 그러기에는 입력값 범위가 너무 크다 -> DP로 해야한다.
int[] dp = new int[n+1];
dp[0]=0;
dp[1]=1;
dp[2]=2;
for(int i=3; i<dp.length; i++){
dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
}
return dp[n];
}
}
DP문제의 기본중에 기본이다..!