text: Number of paths with exactly k coins | A Dynamic Programming based C ++ program to count paths with exactly ' k ' coins ; Base cases ; If this subproblem is already solved ; ( m , n ) can be reached either through ( m - 1 , n ) or through ( m , n - 1 ) ; This function mainly initializes dp [ ] [ ] [ ] and calls pathCountDPRecDP ( ) ; Driver Program to test above functions
code: #include <bits/stdc++.h> NEW_LINE #define R  3 NEW_LINE #define C  3 NEW_LINE #define MAX_K  1000 NEW_LINE using namespace std ; int dp [ R ] [ C ] [ MAX_K ] ; int pathCountDPRecDP ( int mat [ ] [ C ] , int m , int n , int k ) { if ( m < 0 n < 0 ) return 0 ; if ( m == 0 && n == 0 ) return ( k == mat [ m ] [ n ] ) ; if ( dp [ m ] [ n ] [ k ] != -1 ) return dp [ m ] [ n ] [ k ] ; 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 ] ; } int pathCountDP ( int mat [ ] [ C ] , int k ) { memset ( dp , -1 , sizeof dp ) ; return pathCountDPRecDP ( mat , R - 1 , C - 1 , k ) ; } int main ( ) { int k = 12 ; int mat [ R ] [ C ] = { { 1 , 2 , 3 } , { 4 , 6 , 5 } , { 3 , 2 , 1 } } ; cout << pathCountDP ( mat , k ) ; return 0 ; }