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
Read full article from 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];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]);}