[DP] 백준 10844. 쉬운계단 (feat.이차원 배열) - ing

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

# d[x][y]
# x = 자리수
# y = 앞에오는 숫자?
# d[2][2] = d[1][1] + d[1][3]
# d[3][2] = d[2][1] + d[2][3]

for k in range(1,10):
    d[1][k] = 1


for i in range(2,n+1):
    for j in range(10):

        if j == 0:
            d[i][j] = d[i-1][1]
        elif j == 9:
            d[i][j] = d[i-1][8]
        else:
            d[i][j] = d[i-1][j-1] + d[i-1][j+1]
mod = 1000000000
print(sum(d[n]) % mod)