Number of paths with exactly k coins | A Dynamic Programming based Python3 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 ) ; A wrapper over pathCountDPRecDP ( ) ; Driver Code
R = 3 NEW_LINE C = 3 NEW_LINE MAX_K = 1000 NEW_LINE def pathCountDPRecDP ( mat , m , n , k ) : NEW_LINE INDENT if m < 0 or n < 0 : NEW_LINE INDENT return 0 NEW_LINE DEDENT elif m == 0 and n == 0 : NEW_LINE INDENT return k == mat [ m ] [ n ] NEW_LINE DEDENT if ( dp [ m ] [ n ] [ k ] != - 1 ) : NEW_LINE INDENT return dp [ m ] [ n ] [ k ] NEW_LINE DEDENT dp [ m ] [ n ] [ k ] = ( pathCountDPRecDP ( mat , m - 1 , n , k - mat [ m ] [ n ] ) + pathCountDPRecDP ( mat , m , n - 1 , k - mat [ m ] [ n ] ) ) NEW_LINE return dp [ m ] [ n ] [ k ] NEW_LINE DEDENT def pathCountDP ( mat , k ) : NEW_LINE INDENT return pathCountDPRecDP ( mat , R - 1 , C - 1 , k ) NEW_LINE DEDENT k = 12 NEW_LINE dp = [ [ [ - 1 for col in range ( MAX_K ) ] for col in range ( C ) ] for row in range ( R ) ] NEW_LINE mat = [ [ 1 , 2 , 3 ] , [ 4 , 6 , 5 ] , [ 3 , 2 , 1 ] ] NEW_LINE print ( pathCountDP ( mat , k ) ) NEW_LINE