[BAEKJOON] 쉬운 계단 수 - python

쉬운 계단 수

알고리즘 - dynamic programming

n = int(input())

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

for i in range(1,10):
  dp[1][i] = 1 #n=1일때는 1가지

for i in range(2,n+1):
  for j in range(10):
    if j == 0: #마지막이 0일때
      dp[i][j] = dp[i-1][1] 
    elif j == 9: #마지막이 9일때
      dp[i][j] = dp[i-1][8] 
    else: #마지막이 1~8일때
      dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1]

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

N = int(input())

arr = [1]*10 
arr[0] = 0 

for i in range(1, N):
        temp = [0] * 10
        for j in range(10):
            if(j == 0):
                temp[1] += arr[j] # 1이 나올 횟수
            elif(j == 9):
                temp[8] += arr[j] # 9가 나올 횟수
            else:
                temp[j - 1] += arr[j]
                temp[j + 1] += arr[j]

        arr = temp
print(sum(arr) % 1000000000)