Suppose I have a NxN grid (or matrix) and each entry has integers. There is a standard DP problem where you want to find the maximum sum path from top left corner and bottom right corner, using only 'down' and 'right' moves, which can be solved in quadratic time. But I have a modified version of the problem, which states that I start from top left and reach bottom right, using 'down' and 'right' moves, and from there, I have to return back to top left again using 'up' and 'left' moves, and I want to find the maximum sum path. The restriction here is that you're allowed to visit entries that have already been visited by the first path you traversed from top left corner to bottom right corner, but you're not allowed to count that integer since you don't want to double count.
I want to solve this problem using DP though. I've been thinking about this for hours and couldn't come up with a solution. What would be a good way to start? The first thing I tried is find the maximum path from top left to bottom right corner, set all entries of the path to 0, rotate the grid, and do the same thing, and add those paths together, which clearly does not work. I'm having difficulty how to formulate subproblems. PLEASE PLEASE do not post any solutions here.
I won't. But I hope this will be as well an answer, since I wrote this to be an hint.
Think "bottom-up", not from left-top to right-bottom but the opposite. In fact, what you get arriving at the (i-th, j-th) element is the sum between what you already got and the maximum you can get from there.
And the maximum you can get at the (i-th, j-th) element is the maximum you can get to its right and below neighbour.. so..
Notice that the second time you are allowed just to make the opposite moves.. so what is the best path? You can easily understand this by just looking at what are the possible paths.. (maybe the same)..See Edit2.
Hope this could clear how to procede a bit, without spoilering.
Suppose this is the matrix:
$$\begin{matrix}1,0,3\\2,1,6\\1,0,5\\\end{matrix} $$
Starting from bottom (2,2), well you can just get 5. At (2,1) you can get 0+(2,2) so 5, while at (1,2) you can get 6+(2,2) so 11:
$$\begin{matrix}0,0,0\\0,0,11\\0,5,5\\\end{matrix} $$
Next step, what you can get at (2,0) is only 1 + (2,1) so 6, and what you can get at (0,2) is only 3 + (1,2) so 14. But, hey! in (1,1) you have two choices: 1 + (2,1) or 1 + (1,2).. What is the best?
Iterating this process you get the maximum sum from top-left to bottom-right in the top-left column:
$$\begin{matrix}15,12,14\\14,12,11\\6,5,5\\\end{matrix} $$
Hope it's clear now..
(about the bottom-right to top-left.. well it is the same path)Well, in this case the path it is not the same. But the algorithm is this.. just repeat it setting to zero the values you have already took :)
$$ \begin{matrix} 1,1,1,1\\ 1,1,1,1\\ 1,1,1,1\\ 1,1,1,1\\ \end{matrix} $$
Top-left to Bottom-right. $$ \begin{matrix} 7,6,5,4\\ 6,5,4,3\\ 5,4,3,2\\ 4,3,2,1\\ \end{matrix} $$
So the maximum is 7.
Next step (removing the values took.. seven 1s):
$$ \begin{matrix} 0,1,1,1\\ 0,1,1,1\\ 0,1,1,1\\ 0,0,0,0\\ \end{matrix} $$
Again: $$ \begin{matrix} ?,5,4,3\\ 4,4,3,2\\ 3,3,2,1\\ 0,0,0,0\\ \end{matrix} $$
Well. In ? you have to choose the maximum. So 0 + 5 or 0 + 4? Of course 5.
The maximum therefore is 5. 7 + 5 = 12.