10844번 쉬운 계단 수

동적 계획법(Dynamic Programming)을 사용해서 문제를 해결해 보자.

길이가 n이고 마지막 숫자가 0에서 9까지 각각인 계단 수의 개수를 dp[n][last]라고 할 때, 

• (dp[1][0] = 0) (길이가 1이고 마지막 숫자가 0인 계단 수는 없다.)
• (dp[1][i] = 1) (1<= i <= 9), 길이가 1이고 마지막 숫자가 (i)인 계단 수는 1개
• (dp[n][0] = dp[n-1][1])
• (dp[n][9] = dp[n-1][8])
• (dp[n][i] = dp[n-1][i-1] + dp[n-1][i+1]) ((1 <= i <= 8))
• (dp[n][0])에서 (dp[n][9])까지의 합하면(sum(dp[n]) 답이 된다

n = int(input())
dp = [[0] * 10 for _ in range(n+1)]

for i in range(1, 10):
    dp[1][i] = 1

for i in range(2, n+1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][1]
        elif j == 9:
            dp[i][j] = dp[i-1][8]
        else:
            dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1]

print(sum(dp[-1])%(10**9))