[python/バックアップ/DP]9095:1,2,3プラス

1、2、3を合わせる

質問する

整数4を1、2、3の和と表す方法は全部で7種類ある.和を表すときは1つ以上の数を使います.
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
整数nが与えられると、nが1、2、3の和で表される方法の数を求めるプログラムが作成される.

入力

第1行は、試験例の個数Tを与える.各試験例は1行からなり、整数nが与えられる.nは正数で11未満である.

しゅつりょく

各試験例は、nが1,2,3の和を表す方法数を出力する.

に答える

nが1、2、3の和を表す場合
下図のように、4つ以上の数字から同じ数字を繰り返すことが確認できます.

すなわち、dp[n]は、dp[n−1]+1、dp[n−2]+2、dp[n−3]+3を含む(ただし、n>3).
従って,方法の数はdp[n]=dp[n−1]+dp[n−2]+dp[n−3](ただし,n>3)である.
上記の内容に基づいて実現されるコードは以下の通りである.

コード#コード#

t = int(input())
dp = [0,1,2,4]

for i in range(4,11):
    dp.append(dp[i-1]+dp[i-2]+dp[i-3])

for i in range(t):
    n = int(input())
    print(dp[n])