Number of paths with exactly k coins - GeeksforGeeks

Number of paths with exactly k coins - GeeksforGeeks
Given a matrix where every cell has some number of coins. Count number of ways to reach bottom right from top left with exactly k coins. We can move to (i+1, j) and (i, j+1) from a cell (i, j).

X. use a 3 dimensional table dp[m][n][k] where m is row number, n is column number and k is number of coins

int dp[R][C][MAX_K];

http://ideone.com/4I6ubk

 

int pathCountDPRecDP(int mat[][C], int m, int n, int k)

{

    // Base cases

    if (m < 0 || n < 0) return 0;

    if (m==0 && n==0) return (k == mat[m][n]);

 

    // If this subproblem is already solved

    if (dp[m][n][k] != -1) return dp[m][n][k];

 

    // (m, n) can be reached either through (m-1, n) or

    // through (m, n-1)

    dp[m][n][k] = pathCountDPRecDP(mat, m-1, n, k-mat[m][n]) +

                  pathCountDPRecDP(mat, m, n-1, k-mat[m][n]);

 

    return dp[m][n][k];

}

 

// This function mainly initializes dp[][][] and calls

// pathCountDPRecDP()

int pathCountDP(int mat[][C], int k)

{

    memset(dp, -1, sizeof dp);

    return pathCountDPRecDP(mat, R-1, C-1, k);

}

// Recursive function to count paths with sum k from

// (0, 0) to (m, n)

int pathCountRec(int mat[][C], int m, int n, int k)

{

    // Base cases

    if (m < 0 || n < 0) return 0;

    if (m==0 && n==0) return (k == mat[m][n]);

 

    // (m, n) can be reached either through (m-1, n) or

    // through (m, n-1)

    return pathCountRec(mat, m-1, n, k-mat[m][n]) +

           pathCountRec(mat, m, n-1, k-mat[m][n]);

}

Read full article from Number of paths with exactly k coins - GeeksforGeeks