10844単純階段数

https://www.acmicpc.net/problem/10844
ダイナミックプランニングで問題を解くことができます
例えば、3で始まる3桁の数字は以下のようになります

321
323
343
345

でもよく見ると3で始まる3桁の階段数で
(2から始まる2桁の数字で作れる階段数)+(4から始まる2桁の数字で作れる階段数)
これを一般化すると、jjjで始まるiiiビット数の次数として以下のようにすることができる
j路 スタート 座席 数値= スタート 座席 数値)+(j+1 スタート 座席 数字)jtext{先頭の}itext{プレースホルダ}=(j-1text{先頭の}i-1text{プレースホルダ})+(j+1text{先頭の}i-1text{プレースホルダ})j スタート 座席 数値= スタート 座席 数値)+(j+1 スタート 座席 数値)
したがって、このjjjで始まるiiiビット数の次数をdpdpとして注釈すると、dpdpは以下のように一般化することができる
dp[i][j]=dp[i−1][j−1]+dp[i+1][j+1]dp[i][j] = dp[i-1][j-1] + dp[i+1][j+1]dp[i][j]=dp[i−1][j−1]+dp[i+1][j+1]
ただし9で始まるiii桁の数字では、9→109→109→10は不可能なので、9→89→89→8を足すだけです
dp[i][j]=dp[i−1][j−1],if j+1>=10dp[i][j] = dp[i-1][j-1]\quad\text{,if } j+1 >= 10dp[i][j]=dp[i−1][j−1],if j+1>=10
実際に計算すると、dpより前の桁数に、小数+大数から始まるdp値を1つ取って、合算すればいいのです

これでN個目まで求めればいいです.

したがって,n行目の偽数をすべて加算すればよいが,注意すべき点はゼロからではなく,dp[0]を除いて加算すればよい.
output=∑19dp[N][j]output =\sum_1^9dp[N][j]output=∑19​dp[N][j]
これを実現するPythonコードは以下の通りです

import sys

N = int(input())
dp = [[1 for i in range(10)] for j in range(N+1)]

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

r = 0
for i in range(1, 10):
    r = (r + dp[N][i]) % 1000000000

print(r)