Backjun-DP(#9461)

https://www.acmicpc.net/problem/9461
右図に示すように、三角形は螺旋状に並んでいます.最初の三角形は正の三角形で、辺の長さは1です.次に、次の手順で正三角形を追加します.スパイラル上の最長エッジの長さがkの場合、そのエッジにkの長さの正三角形を追加します.
波数の半数列P(N)は螺旋上の正三角形の辺の長さである.Nが与えられた場合、P(N)を求めるプログラムを作成してください.

Code

T = int(input())

dp = [1,1,1,2,2]
for i in range(T):
    n = int(input())
    
    l = len(dp)
    while n > l:
        dp.append(dp[l-1]+dp[l-5])
        l += 1

    print(dp[n-1])

リファレンス
複数のテストケースを実行し、テストケースから取得したdpリストを保存します.他のテストケースでは、不要な重複を低減し、効率を向上させます.