-1

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.

Ted
  • 365
  • Quick sanity check: are you sure this problem is dynamically programmable? The additional constraint of being (effectively) unable (or very limitedly able) to use the same nodes in both directions introduces dependencies that DP doesn't handle well, and it's not even clear to me that this problem isn't 'formally' hard... – Steven Stadnicki Sep 15 '17 at 21:07
  • @Steven Stadnicki. Yes it turns out it can be solved by DP in O(N^4) time. The restriction I made here is what I basically assumed from the problem instruction (not 100% sure, I just emailed him about it and am still waiting for my professor's reply). My original instruction n by n grid, each entry corresponds to number of strawberries, and I want to find the maximum sum path(I collect all strawberries on the path). This is why I assumed revising nodes shouldn't be taken into account when we take sum. – Ted Sep 15 '17 at 21:42
  • I have a typo in the last sentence. *revisiting – Ted Sep 15 '17 at 21:51

1 Answers1

0

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.

What would be a good way to start?

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..

I have to return back to top left again using 'up' and 'left' moves, and I want to find the maximum sum path.

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.

Edit: super simple example to clarify a bit (seen the comment)

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)

Edit2: I didn't understood the restriction.

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 :)

Edit3: Example with 4 square matrix of 1s (because of the comment).

$$ \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.

aterpin
  • 23
  • Not sure if I understand your hint. What do you mean by 'the sum between what you already got and the maximum you get from there'? Also, 'the maximum you can get I,j is the maximum you can get to its right and below its neighbor.' This is not true. Let opt(i ,j) be maximum sum path starting at i,j and back to i,j again (top left - bottom right - top left). To the right I have opt (i,j+1) and down I have opt(i-1,j). You can't just take max between these two because the candidate path could be (i,j) - (i,j+1) - ... - (i-1,j) - (I,j). – Ted Sep 16 '17 at 15:01
  • So definitely opt (I,j) js not correct formulation of suboriblems – Ted Sep 16 '17 at 15:07
  • I think you should consider just one path, because the optimum path top-left to bottom-right is the same you should take bottom-right to top-left. So you just take twice what you can get from top-left to bottom-right. – aterpin Sep 16 '17 at 15:21
  • I think you missed the restriction. If two subpaths intersect at some entry, you only count it once, not twice. – Ted Sep 16 '17 at 15:27
  • I should have fixed and clarified all now, tell me if not. – aterpin Sep 16 '17 at 15:32
  • If I'm not mistaken, you mean I first find the path from top left to the bottom right, and set all entries of the path to zero, and re-run the algorithm and add those numbers together. Unfortunately, this doesn't work. Consider 4 by 4 matrix, with all entries being 1. The optimal path has weight 12. The algorithm may choose the path as follows: (1,1) -> (1,2) -> (1,3) -> (2,3) -> (3,3) -> (4,3) -> (4,4), with weight 7 (Any path from top left to bottom right would give 7). Now set them to 0, and see what happens. In total, this would give me a path of weight 11. – Ted Sep 16 '17 at 15:51
  • Mmm with paper and pencil it works with your example. If you want i add it to the answer. The maximum should be 12, isn't it? – aterpin Sep 16 '17 at 15:51
  • Just edited my comment above. – Ted Sep 16 '17 at 15:54
  • A square matrix with seven 0s and nine 1s gives a path of weight 5. 5+7 gives 12. Just tell me if you need to see it, i will edit the answer. – aterpin Sep 16 '17 at 15:54
  • In my previous comment, I gave an example with a path of weight 7 from top left to bottom right. Then this forces the following path to be at most 4. 7 + 4 = 11 – Ted Sep 16 '17 at 16:03
  • In addition, this problem is expected to be solved in O(n^4) time so definitely not our approach :) – Ted Sep 16 '17 at 16:09
  • This is two times NM (or NN), so roughly O(N^2). How to implement stands to you. – aterpin Sep 16 '17 at 16:13