[백준] 10844 쉬운 계단 수

dp를 이차원 배열로 정의해야하는 문제였다.
i는 자리수, j는 시작하는 수이며 dp[i][j]는 dp[i-1][j-1] 앞에 j를 붙이고 dp[i-1][j+1] 앞에 j를 붙여서 만들 수 있다. 따라서 j=0인 경우에는 dp[i-1][1]과 j=9인 경우에는 dp[i-1][8]만 고려해주면 된다. 0으로 시작하는 수는 없다고 나와있지만 표는 0까지 포함해야만 값을 찾을 수 있었다.
int로 정의하면 오버플로우가 날 수 있기 때문에 long으로 정의하고, 1,000,000,000으로 나눠주는 것도 잊어서는 안된다.

점화식: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

public class Solution10844 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // 테이블 정의
        long dp[][] = new long[n+1][10];

        // 초기값 설정
        for(int i = 0; i < 10; i++) {
            dp[1][i] = 1;
        }

        //점화식 정의
        for(int i = 2; i < n+1; i++) {
            dp[i][0] = dp[i-1][1] % 1000000000;
            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] % 1000000000;
        }
        long result = 0;
        for (int i = 1; i < 10; i++) {
            result += dp[n][i]%1000000000;
        }
        System.out.println(result%1000000000);
    }
}