Calculate rest path sum of weight matrix
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