[アルゴリズム/標準]1057:上り坂数(python)

最後に何とかして解決した.
12311232136314104151551621617287183681945911055

0で終了するには、前の数は024579182です.

1で終了する場合、移行数は1未満になります.

2で終了するには、移行数が2未満である必要があります.
...

9で終わるには、移行数が8以下です...
状況の数を合わせると答えが出る.

ex) dp[i][9] = dp[i-1][8] + dp[i-1][7] + dp[i-1][6] + dp[i-1][5] + dp[i-1][4] + dp[i-1][3] + dp[i-1][2] + dp[i-1][1] + dp[i-1][0]

N = int(input())
dp = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] for _ in range(N+1)]
dp[1] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for i in range(2, N + 1):
    dp[i][0] = 1
    s = 1
    for j in range(1, 10):
        s += dp[i-1][j]
        dp[i][j] = s % 10007
print(sum(dp[N]) % 10007)