簡単な階段

5867 ワード
シルバー パイ アルゴリズム#アルゴリズム# DP テキストリンク

質問する



インプット


import sys
input = sys.stdin.readline
n = int(input())
res = [[0] * 10 for i in range(n+1)]
res[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(2, n+1):
    res[i][0] = res[i-1][1]
    res[i][9] = res[i-1][8]
    for j in range(1, 9):
        res[i][j] = res[i-1][j-1]+res[i-1][j+1]
print(sum(res[n]) % 1000000000)

説明:


1桁の次数は1,2,3,4,5,6,7,8,9の計9個である
0で始まることができないので、前列が0の場合、01、012などです.
階段数ではありません
ルールを簡単に見ると、配列の中でdp[i][n]、iはビット数nから0から9
dp[i][n]=dp[i-1][n-1]+dp[i-1][n+1]のルールが現れた.
ただし、n=0,n=9であれば、ルールによって異なります
n=0はdp[i-1][n+1]、n=9はdp[i-1][n-1]を表す
このような規定があります.

画像の説明



ポスト


2 D配列でdpを使うとは思わなかった...
最終的に答えを見て理解し、コードを見ずに実現しました.
点火式の探し方にはまだ慣れていないようです.
DP問題は最終的に点火式を求めますが、多くのタイプの問題を解く必要がありますか?
Javascript, HTML, CSS
レポートの一括印刷要件の実現方法