백준 10844번

동적 계획법 단계의 문제를 열심히 풀고 있습니다.

계단 수란 다음 자릿수가 1의 차이를 가지고 이어지는 수입니다

예를들면 3456, 210 등이 있겠습니다.

다이나믹 프로그래밍으로 풀었습니다.

자릿수 N으로 4가 주어졌을 경우 첫번째 숫자의 다음 자리 수는 첫번째 숫자에서 1을 더하거나, 1을 뺀 수가 와야 합니다.

첫번째 숫자가 3일 경우, 다음 자리에 올 수 있는 계단 수는 2와 4인것입니다.

메모제이션 된 2와 4의 값을 더하면 쉽게 현재의 계단 수 개수를 구할 수 있습니다.

0과 9의 경우 다음 자리에 올수있는 숫자가 1과 8로 한정적입니다. 이 경우만 케이스를 분류해서 따로 계산합니다.

#include <cstdio>
 
int main() {
    int n;
    int div = 1000000000;
    scanf("%d", &n);
 
    int** dp = new int*[n+1];
    for (int i = 0; i <= n; i++) {
        dp[i] = new int[10];
    }
 
    for (int i = 0; i < 10; i++) {
        dp[1][i] = 1;
    }
 
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 10; j++) {
            if (j == 0) {
                dp[i][j] = dp[i - 1][1] % div;
            }
            else if (j == 9) {
                dp[i][j] = dp[i - 1][8] % div;
            }
            else {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % div;
            }
        }
    }
 
    int sum = 0;
    for (int i = 1; i < 10; i++) {
        sum = (sum + dp[n][i]) % div;
    }
 
    printf("%d\n", sum);
}