I have another DP approach where the problem can be reduced to a standard maximum-sum grid DP.
Consider the three arrays as a 3×N matrix.
Notice that from (r,c), the only allowed moves are (r,c+1) and (r+1,c+1) We can compute this easily , since there is only 3 rows and N col. in o(N)
I have another DP approach where the problem can be reduced to a standard maximum-sum grid DP.
Consider the three arrays as a 3×N matrix.
Notice that from (r,c), the only allowed moves are (r,c+1) and (r+1,c+1) We can compute this easily , since there is only 3 rows and N col. in o(N)