10844 쉬운 계단 수

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.InputStreamReader;
import java.io.IOException;

public class main {
	static long[][] dp;
	static int N;
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	N = Integer.parseInt(br.readLine());
    	
    	dp = new long [N+1][10]; //N: 자리수
    	
    	for(int i=1; i<10; i++) {
    		dp[1][i] = 1L;
    	}
    	for(int i=2; i<=N; i++) {
    		dp[i][0] = dp[i-1][1];
    		for(int j=1; j<9; j++) {
    			dp[i][j]= (dp[i-1][j-1]+dp[i-1][j+1])%1000000000;
    		}
    		dp[i][9] = dp[i-1][8];
    	}
    	long answer=0;
    	for(int i=0; i<=9; i++) {
    		answer+=dp[N][i]%1000000000;
    	}
    	bw.write(answer%1000000000+"\n");
    	bw.flush();
    	bw.close();
    }
}

너무 dp 문젠데 알아채지 못했다.. 진짜 많이 풀어봐야겠다 양치기 가겠슴돠~