[伯俊]9095号:1.2.3加号問題

質問リンク
https://www.acmicpc.net/problem/9095
解き方

整数4の数字は7(1+2+4)、5の数字は13(2+4+7)です.

従って、整数Nの個数は(N−3)+(N−2)+(N−1)の和であり、以下のような点火式を確立することができる.
てんかしき
dp[n] = dp[n-3] + dp[n-2] + dp[n-1]
or
dp[n] = sum(dp[i-3:i])
完全なコード

T = int(input())
for _ in range(T):
    N = int(input())
    dp = [1, 2, 4]
    for i in range(3, N):
        dp.append(sum(dp[i-3:i]))
    print(dp[N-1])