Min Cost Path | DP | A Naive recursive implementation of MCP ( Minimum Cost Path ) problem ; A utility function that returns minimum of 3 integers ; Returns cost of minimum cost path from ( 0 , 0 ) to ( m , n ) in mat [ R ] [ C ] ; Driver program to test above functions
R = 3 NEW_LINE C = 3 NEW_LINE import sys NEW_LINE def min ( x , y , z ) : NEW_LINE INDENT if ( x < y ) : NEW_LINE INDENT return x if ( x < z ) else z NEW_LINE DEDENT else : NEW_LINE INDENT return y if ( y < z ) else z NEW_LINE DEDENT DEDENT def minCost ( cost , m , n ) : NEW_LINE INDENT if ( n < 0 or m < 0 ) : NEW_LINE INDENT return sys . maxsize NEW_LINE DEDENT elif ( m == 0 and n == 0 ) : NEW_LINE INDENT return cost [ m ] [ n ] NEW_LINE DEDENT else : NEW_LINE INDENT return cost [ m ] [ n ] + min ( minCost ( cost , m - 1 , n - 1 ) , minCost ( cost , m - 1 , n ) , minCost ( cost , m , n - 1 ) ) NEW_LINE DEDENT DEDENT cost = [ [ 1 , 2 , 3 ] , [ 4 , 8 , 2 ] , [ 1 , 5 , 3 ] ] NEW_LINE print ( minCost ( cost , 2 , 2 ) ) NEW_LINE