Min Cost Path | DP | Dynamic Programming Python implementation of Min Cost Path problem ; Instead of following line , we can use int tc [ m + 1 ] [ n + 1 ] or dynamically allocate memoery to save space . The following line is used to keep te program simple and make it working on all compilers . ; Initialize first column of total cost ( tc ) array ; Initialize first row of tc array ; Construct rest of the tc array ; Driver program to test above functions
R = 3 NEW_LINE C = 3 NEW_LINE def minCost ( cost , m , n ) : NEW_LINE INDENT tc = [ [ 0 for x in range ( C ) ] for x in range ( R ) ] NEW_LINE tc [ 0 ] [ 0 ] = cost [ 0 ] [ 0 ] NEW_LINE for i in range ( 1 , m + 1 ) : NEW_LINE INDENT tc [ i ] [ 0 ] = tc [ i - 1 ] [ 0 ] + cost [ i ] [ 0 ] NEW_LINE DEDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT tc [ 0 ] [ j ] = tc [ 0 ] [ j - 1 ] + cost [ 0 ] [ j ] NEW_LINE DEDENT for i in range ( 1 , m + 1 ) : NEW_LINE INDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT tc [ i ] [ j ] = min ( tc [ i - 1 ] [ j - 1 ] , tc [ i - 1 ] [ j ] , tc [ i ] [ j - 1 ] ) + cost [ i ] [ j ] NEW_LINE DEDENT DEDENT return tc [ m ] [ n ] NEW_LINE DEDENT cost = [ [ 1 , 2 , 3 ] , [ 4 , 8 , 2 ] , [ 1 , 5 , 3 ] ] NEW_LINE print ( minCost ( cost , 2 , 2 ) ) NEW_LINE