Calculate rest paht sum of weight matrix
for ( int i = 1 ; i < N ; i ++ ) for ( int j = 1 ; j < i + 1 && j < N ; j ++ ) dp [ i ] [ j ] = mat [ i ] [ j ] + max ( dp [ i - 1 ] [ j - 1 ] , dp [ i - 1 ] [ j ] ) ;