#dp의 가로를 자리수, 세로를 해당 자리의 숫자로 했을 때
n = int(input())
dp = [[0]*n for _ in range(10)]
for i in range(1,10):
    dp[i][0] = 1
for i in range(10):
    for j in range(1,n):
        if i > 0:
            dp[i][j] += dp[i-1][j-1]
        if i < 9:
            dp[i][j] += dp[i+1][j-1]
ans = 0
for i in range(10):
    ans += dp[i][n-1]
print(ans%1000000000)

#dp의 가로를 해당 자리의 숫자, 세로를 자리수로 정했을 때
n = int(input())
dp = [[0]*10 for _ in range(n)]
for i in range(10):
    dp[0][i] = 1
for i in range(1,n):
    for j in range(10):
        if j > 0:
            dp[i][j] += dp[i-1][j-1]
        if j < 9:
            dp[i][j] += dp[i-1][j+1]
ans = 0
for i in range(1,10):
    ans += dp[-1][i]
print(ans%1000000000)

후자는 맞고 전자는 계속 틀리는데 아무리 생각해 봐도 논리상에는 문제가 없는 것 같아서 질문드립니다.
왜 틀린 걸까요??
대답해주시면 진심으로 감사하겠습니다.