You are given an M * N grids (1 <= M, N <= 100). You start from the most left-top cell (0, 0) and want to get to the most right-bottom cell (M-1, N-1). At any time, you can only move to left, right or down. Each cell (mij) contains an integer between -100 and 100 (inclusive) denoting the value that you will received when you visit the corresponding cell, in such manners:
- mij = mij for the first visit to cell (i, j)
- mij = -|mij| for each next visit to cell (i, j)
Calculate the maximum value that can be achieved to reach cell (M-1, N-1)!
There is an easier (and more popular) version, where you can only move to right or down, that can be solved by dynamic programming. You might want to try the easier version first if you’re new to dynamic programming.
To solve this problem, define a dynamic programming state as f(r, b): the maximum value that can be achieved at row r when you want to move down at column b (b is the last column that you visit at row r). Then f(M-1, N-1) is the value that you want to find. To solve f(r, b), you need to try all a from 0 to N-1 as the first visited column when you arrive at row r, in which you can use f(r-1, a) to get the optimal value for the previous state. Example of an optimal move at row r which start from column a and end at column b is shown in the figure below.
L(b) and R(a) are the “expansion” moves where the cells are being visited twice, except the last cells (the end/turning point).
Then the state can be written as:
warning: the above formula might contains some minor mistakes.
S(a, b) is the partial sum of each value at row r from column a to column b.
T(a, b) is the partial sum of each absolute value at row r from column a to column b.
L(k) is the maximum value that can be achieved at row r by moving left from column k and return back to column k.
R(k) is the maximum value that can be achieved at row r by moving right form column k and return back to column k.
You should notice the exception in the above formula for the first row (r = 0), i.e. you should start only from a = 0 instead of trying all a from 0 to N-1.
S, T, L and R for each r can be precalculated, so the overall time-complexity for this solution is O(M*N2), or O(N3) when N = M.