[Python] 10844번

동적프로그래밍
1. Top-down: 메모이제이션
2. Buttom-up :상향식 계산법

       0 1 2 3 4 5 6 7 8 9
1개    0  1 1 1 1 1 1 1 1 1 
2개    1  1 2 2 2 2 2 2 2 1
3개    1  3 3 4 4 4 4 4 3 2
4개    3  4 7 7 8 8 8 7 6 3

dp = [[]for _ in range(N)]
dp[0] = [0,1,1,1,1,1,1,1,1,1]
dp[1] = [dp[1],dp[0]+dp[2],dp[1]+dp[3]....]

import sys

N = int(sys.stdin.readline())
dp = [[0 for col in range(10)] for _ in range(N)]
dp[0] = [0,1,1,1,1,1,1,1,1,1]

for i in range(N):
   if i ==0:
       continue
   else:
       dp[i] = [dp[i-1][1],dp[i-1][0]+dp[i-1][2],dp[i-1][1]+dp[i-1][3],dp[i-1][2]+dp[i-1][4],dp[i-1][3]+dp[i-1][5],dp[i-1][4]+dp[i-1][6],dp[i-1][5]+dp[i-1][7],dp[i-1][6]+dp[i-1][8],dp[i-1][7]+dp[i-1][9],dp[i-1][8]]
s=0
for i in dp[N-1]:
   s+=i
print(s % 1000000000)

import sys

N = int(sys.stdin.readline())
dp = [[0 for col in range(10)] for _ in range(N)]
dp[0] = [0,1,1,1,1,1,1,1,1,1]

for i in range(N):
    if i ==0:
        continue
    else:
        for k in range(10):
            if k == 0:
                dp[i][k] = dp[i-1][1]
            elif k==9:
                dp[i][k] = dp[i-1][8]
            else:
                dp[i][k] = dp[i-1][k-1]+dp[i-1][k+1]

s=0
for i in dp[N-1]:
    s+=i
print(s % 1000000000)