Maximum weight path ending at any element of last row in a matrix | Python3 program to find the path having the maximum weight in matrix ; Function which return the maximum weight path sum ; creat 2D matrix to store the sum of the path ; Initialize first column of total weight array ( dp [ i to N ] [ 0 ] ) ; Calculate rest path sum of weight matrix ; find the max weight path sum to reach the last row ; return maximum weight path sum ; Driver Program
MAX = 1000 NEW_LINE def maxCost ( mat , N ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( N ) ] for j in range ( N ) ] NEW_LINE dp [ 0 ] [ 0 ] = mat [ 0 ] [ 0 ] NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT dp [ i ] [ 0 ] = mat [ i ] [ 0 ] + dp [ i - 1 ] [ 0 ] NEW_LINE DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT for j in range ( 1 , min ( i + 1 , N ) ) : NEW_LINE INDENT dp [ i ] [ j ] = mat [ i ] [ j ] + max ( dp [ i - 1 ] [ j - 1 ] , dp [ i - 1 ] [ j ] ) NEW_LINE DEDENT DEDENT result = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( result < dp [ N - 1 ] [ i ] ) : NEW_LINE INDENT result = dp [ N - 1 ] [ i ] NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT mat = [ [ 4 , 1 , 5 , 6 , 1 ] , [ 2 , 9 , 2 , 11 , 10 ] , [ 15 , 1 , 3 , 15 , 2 ] , [ 16 , 92 , 41 , 4 , 3 ] , [ 8 , 142 , 6 , 4 , 8 ] ] NEW_LINE N = 5 NEW_LINE print ( ' Maximum ▁ Path ▁ Sum ▁ : ' , maxCost ( mat , N ) ) NEW_LINE