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