A cricketer can score 1, 2, 4 or 6 in a ball. Find in how many ways the player can score a total of "n" runs without hitting 3 consecutive boundaries. Note: Scoring 4 or 6 is considered as a boundary.
My solution is:
int *arr; //global array to save calculated ways
int waysUtil(int n, int boundaries){
if(n==0)
return 1;
if(n<1)
return 0;
if(arr[n]>0)
return arr[n];//if already calculated return the value
int hit_one = waysUtil(n-1, 0);
if(n-1 >=0) arr[n-1]= hit_one;
int hit_two = waysUtil(n-2, 0);
if(n-2 >=0) arr[n-2] = hit_two;
int hit_four=0, hit_six=0;
// for 4 and 6 check number of consecutive boundaries hit.
//if less than two then calculate
if(boundaries<2 ){
hit_four = waysUtil(n-4, boundaries + 1);
if(n-4 >=0) arr[n-4] = hit_four;
hit_six = waysUtil(n-6, boundaries + 1);
if(n-6 >=0) arr[n-6] = hit_six;
}
return hit_one + hit_two + hit_four + hit_six;
}
int ways(int score){
arr =(int*)malloc(sizeof(int)*score);
memset(arr, -1, sizeof(arr));
int noOfWays = waysUtil(score, 0);
free(arr);
return noOfWays;
}
Is better solution possible?