aeonary's blog

Maximum path in a grid
By aeonary, history, 11 months ago, In English

Given a grid of size $$$M \times N, (1 \le M, N \le 2000)$$$ where each cell contains an integer $$$A_ij, (|A_ij| \le 250)$$$. We have to find the maximum path from (1, 1) to any cell in the last row. Allowed moves are right, left, and bottom.

I've used DP to solve this problem, where $$$DP[i][j]$$$ equals the maximum path sum from (1, 1) to (i, j). Then I got 2 cases: the first one is that we can get to (i, j) from (i — 1, j), and from (i, j) we can move left or right such that the left sum and the right sum is positive, so initially, $$$DP[i][j] = DP[i-1][j] + A[i][j] + maxPrefix[i][j - 1] + maxSuffix[i][j + 1]$$$. Cases number 2 is that we can get to (i, j) from (i, k), and (i, k) is from (i — 1, k), and then from (i, k) we can move to the left if $$$k < j$$$, then move to the right of j: $$$DP[i][j] = DP[i - 1][k] + sum[j..k] + maxPrefix[i][k - 1] + maxSuffix[i][j + 1]$$$ or we can move to the right from (i, k) if $$$j < k$$$, then move to the left of j: $$$DP[i][j] = DP[i - 1][k] + sum[j..k] + maxPrefix[i][j - 1] + maxSuffix[i][k + 1]$$$. But I got WA with this solution, please help me to solve this problem (sorry that I don't have the submission link).

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my code

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
I think of 2 dps:
                     dp1[i][j] = max ans so far, we come here from (i-1,j) to (i,j)
                                               its is first time we come to ith row  
                     dp2[i][j] = max ans so far, we now go from (i,j) to (i+1 ,j)
                                               its is last time we in the ith row
dp2[i][j] = Max(k<j , dp1[i][k] + sum(A[i][k..j])
                k>j , dp1[i][k] + sum(A[i][j..k])
                k=j , dp1[i][j])
dp1[i][j] = dp2[i-1][j] + A[j]
→ Reply