[BOJ 9461]波涛半数列(Python)

質問リンク

ローブ数列

計画と思考

問題を読む過程で、ルールに従って数列を生成できると思います.

図を見ると、7番目の三角形から1番目の三角形の辺の長さは、i-1個の三角形とi-5個の三角形の辺の長さの和に等しいことが分かった.6番目の三角形までは問題で与えられているので,与えられた値で初期化し,オーバーフローを防止するために十分な配列をした.
その後100番目の三角形までの長さを求めた.
その後test caseのようにnの入出力を実現した.

に答える

import sys
pado = [0,1,1,1,2,2,3] + [0]*100

test_case = int(sys.stdin.readline())
for i in range(7,102):
    pado[i] = pado[i-1] + pado[i-5]
for t in range(test_case):
    n = int(sys.stdin.readline())
    print(pado[n])

説明するときに出会う困難と苦悩。

邪魔したり悩むところはない.

釈義後に知る概念と感想

DP問題は数学的帰納法のように命題を立て,それが成立しているかどうかを確認し,そのまま実施すればよい.だから面白いと思う