Pythonで競プロしてる 
すべての項が3以上の整数で、総和が整数Sであるような数列がいくつあるのか、を求める問題です。
提出
s = int(input())
mod = 10**9+7
dp = [0]*(s+1)
dp[0] = 1
for i in range(1,s+1):
for j in range(0,(i-3)+1):
dp[i] += dp[j]
dp[i] %= mod
print(dp[s])DP（動的計画法）という方法で解いていきます。
整数S=7の場合、区切られる位置は、
|○○○○○○○|
|○○○|○○○○|
|○○○○|○○○|の {7}, {3,4}, {4,3} が条件を満たすため、答えは3になります。
この区切る位置に注目します。
最後に区切る位置をiとしたときの数列の個数dp[i]を求めます。
例えば、「i=3」である場合、
|○○○|○……となるため、dp[3]=1になります。「i=4」では、
|○○○○|○……となり、dp[4]=1となります。
「i=7」の場合、
|○○○○○○○|○……と、「dp[3]+dp[4]」を加えたものが答えになり、dp[7]=3となります。
最後の区切り位置より左側には、3つ以上の◯がないといけないので、「0≦j≦4」のdp[j]を足し合わせる形になります。
（dp[1]とdp[2]は、ともに0です）
提出したプログラムに話を戻します。
すべてのdpに初期値0を代入します。
dp[0]は、1にしておきます。
特定のdp[i]を求めるために、「0≦j≦(i-3)」のdp[j]を使用します。
最終的にdp[s]に入っている数値が答えです。
