(DP)白駿10844号単純階段数

https://pacific-ocean.tistory.com/151

n = int(input())
dp = [[0 for i in range(10)] for j in range(101)]
for i in range(1, 10):
    dp[1][i] = 1
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]) % 1000000000)

各桁数の最下位(0～9)

                 0  1  2  3  4  5  6  7  8  9

桁数(1)0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
ビット数(2)1 1 2 2 2 2 2 2 1
桁数(3)1 3 3 4 4 3 2
上のルールを見てください.ビット数が1の場合、各数字が最後のビットに到達できる個数は
一つずつ.桁数が1なので
桁数が2の時を見てみましょう.
一番後ろに0の数-10がある可能性があります.(1個)
一番後ろに1が現れる可能性のある状況の数-21.(1個)
一番後ろに2の数-12,32が現れる可能性があります.(2個)
このように3桁を求めると、上と同じ表が出てくるので、ルールが見つかれば、
この位置の対角線位置の数字の和であることが分かる.
当たり前のことです.3が一番後ろに行くなら、前は2か4を歩かなければならないからです.
0は左対角線がないので、右対角線しかありません.9も同じですが、右対角線がないので、左対角線しかありません.
このように点火式を確立し,コードを記述する.
ビット数
j=一番後ろの数.(0 ~ 9)
j = 0 dp[i][j] = dp[i - 1][1]
j = 9 dp[i][j] = dp[i - 1][8]
j = 2 ~ 8 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]