copy all element of first column into ' dp ' first column
for ( $ i = 0 ; $ i < $ N ; $ i ++ ) $ dp [ 0 ] [ $ i + 1 ] = $ Mat [ 0 ] [ $ i ] ; for ( $ i = 1 ; $ i < $ N ; $ i ++ ) for ( $ j = 1 ; $ j <= $ N ; $ j ++ ) $ dp [ $ i ] [ $ j ] = max ( $ dp [ $ i - 1 ] [ $ j - 1 ] , max ( $ dp [ $ i - 1 ] [ $ j ] , $ dp [ $ i - 1 ] [ $ j + 1 ] ) ) + $ Mat [ $ i ] [ $ j - 1 ] ;