[DP] python 10844 쉬운 계단

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

# 2023.01.29
import sys
input = sys.stdin.readline

n = int(input()) # 자리수
dp=[[0]*(10) for _ in range(n+1)]
for j in range(1, 10):
    dp[1][j]=1
for i in range(2, n+1):
    for j in range(10):
        if j==0:
            dp[i][j]=dp[i-1][j+1]
        elif j==9:
            dp[i][j]=dp[i-1][j-1]
        else:
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]

print(sum(dp[n])%1000000000)