Min Cost Path | DP | Python3 program for the above approach ; For 1 st column ; For 1 st row ; For rest of the 2d matrix ; Returning the value in last cell ; Driver code
def minCost ( cost , row , col ) : NEW_LINE INDENT for i in range ( 1 , row ) : NEW_LINE INDENT cost [ i ] [ 0 ] += cost [ i - 1 ] [ 0 ] NEW_LINE DEDENT for j in range ( 1 , col ) : NEW_LINE INDENT cost [ 0 ] [ j ] += cost [ 0 ] [ j - 1 ] NEW_LINE DEDENT for i in range ( 1 , row ) : NEW_LINE INDENT for j in range ( 1 , col ) : NEW_LINE INDENT cost [ i ] [ j ] += ( min ( cost [ i - 1 ] [ j - 1 ] , min ( cost [ i - 1 ] [ j ] , cost [ i ] [ j - 1 ] ) ) ) NEW_LINE DEDENT DEDENT return cost [ row - 1 ] [ col - 1 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT row = 3 NEW_LINE col = 3 NEW_LINE cost = [ [ 1 , 2 , 3 ] , [ 4 , 8 , 2 ] , [ 1 , 5 , 3 ] ] NEW_LINE print ( minCost ( cost , row , col ) ) ; NEW_LINE DEDENT