ways to express n as sum of 1 3 4

ways to express n as sum of 1 3 4

  January 25, 2018    

---

import java.util.*;
import java.lang.*;
import java.io.*;
class dmg
 {
static long dp[]=new long[10001];
public static long process(int n)
{
if(n==0)
return 1;
if(dp[n]!=-1)
return dp[n];
long res=0;
 
if(n>=4)
res+=(process(n-4))%1000000007;
if(n>=3)
res+=(process(n-3))%1000000007;
res+=(process(n-1))%1000000007;
return dp[n]=res%1000000007;
}
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();

Arrays.fill(dp,-1);
dp[1]=1;
dp[2]=1;
dp[3]=2;
dp[4]=4;
while(t-->0)
{
    int n=ab.nextInt();
    
    System.out.println(process(n));
}
}
}