#define N 5

int triangle[N][N]={

    { 6,-1,-1,-1,-1},

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

    { 3, 7, 4,-1,-1},

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

    { 2, 7, 5, 9, 4}

};

int cache[N][N];

int n=0;

int path1(int x, int y){

    n++;

    //basis

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

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

    int n1 = path1(x+1,y);

    int n2 = path1(x+1,y+1);

    if(n1>n2){

        return cache[x][y]=triangle[x][y]+n1;

    }else{

        return cache[x][y]=triangle[x][y]+n2;

    }

}

int main(){

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

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

            cache[i][j]=-1;

        }

    }

    printf("%d

",path1(0,0));

    printf("Function called %d times

",n);

}

/**

* 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);

    }

}