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

744 ワード
白駿 DP アルゴリズム#アルゴリズム# 上り坂 python 11057 テキストリンク

最後に何とかして解決した.
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)
    ぶんかつすうじれつ
    Splinter-オープンソースの軽量レベルのフロントエンドテストツール