[BOJ]10844簡単な階段

簡単な階段

に答える

0以外のすべての数字は前にすることができます.
このとき1~8の後ろから来ることができる数字は2種類(数字±1)である.
しかし、9後には数字8しか来ません.

桁数が2の時を見てみましょう。

一番後ろに0の数-10がある可能性があります.(1個)
一番後ろに1が現れる可能性のある状況の数-21.(1個)
一番後ろに2の数-12,32が現れる可能性があります.(2個)
このように3桁を求めると、上と同じ表が出てくるので、ルールが見つかれば、
この位置の対角線位置の数字の和であることが分かる.

コード#コード#

N = int(input())

dp = [[0]*10 for _ in range(N+1)]
for i in range(1, 10):
    dp[1][i] = 1

MOD = 1000000000

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

print(sum(dp[N]) % MOD)