/**

* JumpGame

*/

#define N 7

int gameBoard[N][N]={

    {2,5,1,6,1,4,1},

    {6,1,1,2,2,9,3},

    {7,2,3,2,1,3,1},

    {1,1,3,1,7,1,2},

    {4,1,2,3,4,1,2},

    {3,3,1,2,3,4,1},

    {1,5,2,9,4,7,-1}

};

//int gameBoard[N][N]={

//    {1,1,1,1,1,1,1},

//    {1,1,1,1,1,1,1},

//    {1,1,1,1,1,1,1},

//    {1,1,1,1,1,1,1},

//    {1,1,1,1,1,1,1},

//    {1,1,1,1,1,1,2},

//    {1,1,1,1,1,2,-1},

//};

int n=0;

int footStep[N][N];

bool jumpGame(int x,int y){

    n++;

    //basis

    if(x>=N || y>=N){ return false;}

    if(x== N -1 && y==N-1){return true;}

    if(footStep[x][y]!=-1){ return footStep[x][y];}

    footStep[x][y] = jumpGame(x+gameBoard[x][y],y) || jumpGame(x,y+gameBoard[x][y]);

    return footStep[x][y];

}

int main(){

    for(int i=0;i<N;i++){

        for(int j=0;j<N;j++){

            footStep[i][j]=-1;

        }

    }

    if(jumpGame(0,0)){

        printf("Reached a goal.

");

    }else{

        printf("Not reached a goal.

");

    }

    printf("Function called %d times

",n);

}

/**

* Combination

*/

#define N 4

#define K 2

char parent[K];

void combination(int depth){

    if(depth==K-1){

        for(int i=0;i<K;i++){

            printf("%c ",parent[i]);

        }

        printf("

");

        return;

    }

    for(int i=parent[depth]+1-97;i<N;i++){

        parent[depth+1]=i+97;

        combination(depth+1);

    }

}

int main(){

    for(int i=0;i<N;i++){

        parent[0] = i+97;

        combination(0);

    }

}

#define N 300

int cache[N][N];

int binomial_coefficient(int n, int r){

    //basis example

    if(r==0 || n==r){return 1;}

    if(cache[n-1][r-1]==-1){

        cache[n-1][r-1] = binomial_coefficient(n-1,r-1);

    }

    if(cache[n-1][r] == -1){

        cache[n-1][r] = binomial_coefficient(n-1,r);

    }

    return cache[n-1][r-1]+cache[n-1][r];

}

void main(){

    for(int i=0;i<N;i++){

        for(int j=0;j<N;j++){

        cache[i][j]=-1;

        }

    }

    printf("%d

",binomial_coefficient(250,12));

}