Recusive Dp (Branch & Bound )

Strategy for the World Cup (codechef )

In this question we have to complete a given amount of runs using only 4's and 6's

 we have to say the no. of ways by which we can do this.

 in this question there are four cases

 case 1) run=6    then--->> ball= ball-1 , run=run-6, wicket=wicket

 case 2) run=4     then--->> ball= ball-1 , run=run-4, wicket=wicket
 case 3) run=0     then--->> ball= ball-1 , run=run, wicket=wicket
 case 4) run=out  then--->> ball= ball-1 , run=run, wicket=wicket-1


base case if (run==0 && bal==0 && w>=0 ) this will return 1;







#include<bits/stdc++.h>

using namespace std;

long long  dp[305][1805][15];

long long  solve(long long  b,long long  r,long long  w)
{
  long long  a=0;

  if(r==0 && b==0 && w>=0)
  return 1;

  if(w<0 || b<=0 || r<0)
  return 0;

 if(dp[b][r][w]!=-1)
  {
    return dp[b][r][w];
  }
 
 
 long long  &ret=dp[b][r][w];
   ret=0;


   a=a+solve(b-1,r-6,w);
   a=a%1000000007;

   a=a+solve(b-1,r-4,w);
   a=a%1000000007;

   a=a+solve(b-1,r,w);
   a=a%1000000007;

   a=a+solve(b-1,r,w-1);
   a=a%1000000007;
   return ret=a;

}




int  main()
{
 long long i,j,k;
 //memset(dp,-1,sizeof(dp));
 for(i=0;i<301;i++)
     for(j=0;j<1801;j++)
       for(k=0;k<11;k++)
         dp[i][j][k]=-1;
 long long  t;
 cin>>t;
 while(t--)
 {
  long long  b,r,w,i;
  cin>>r>>b>>w;

  if(r>1800 || r%2==1 )
    cout<<0<<endl;
  else
  cout<<solve(b,r,w)<<endl;
 }
return 0;
}