CODEWITHSUNDEEP
algorithmmatrixdynamic-programming
VB_
VB_

Reputation: 45692

Intresting puzzle

Task definition:

I have a matrix of natural numbers. The task is to find path from the top-left corner of matrix to bottom-right corner of matrix and dial maximum score. Rules of navigation: if you are located in [i][j] you can move: a) to [i][j-1], [i][j+1], [i+1][j] cells and dial zero points b) to [i+1][j+1] and dial matrix[i][j] points

Little example:

Assume you have score 50and matrix

0 3 5 3 2
4 7 2 5 2
4 3 5 2 5

Assume you are in [1][1] cell (matrix[1][1] = 7). You can navigate to:

a) [1][0] cell with 50 score
b) [1][2] cell with 50 score
c) [2][1] cell with 50 score
d) [2][2] cell with 57 score

What a problem:

I solve this task in very slow way...

I try to implement in with help of recursion. It's easy if you just want to find maximum score. Something like 

public int loop(int i, int j) {
  int left = loop(i, j-1);
  int top = loop(i-1, j);
  int diagonal = loop(i-1,j-1) + matrix[i-1][j-1];
  return maximum(left, top, diagonal);
}

BUT, I want to find a path with maximum score! And it's very time/memory consuming.

Why it's time/memory consuming:

And there is one problem: I need store path-collection and pass it as a parameter to the loop method. But loop method forks on each iteration and I have to copy path-collection thee times an iteration. Otherwise, each of loop forks will modify common path-collection and finally I will have in it all possible paths. I mean if between left, top & diagonal the biggest is left that we must not to include paths linked with top and diagonal.

Question:

How to solve it in right way?

EDIT:

Actually there is no need to find the full path. It only need to find point's in which you dial a score (in which you make a diagonal moves)

Upvotes: 2

Views: 257

Answers (2)

Kaushik Shankar
Kaushik Shankar

Reputation: 5619

EDIT: I misread the question to being just moving down and to the right (ie: j could only change to j or j+1.) so this answer is wrong.

You can use dynamic programming to solve this problem. Greedy doesn't exactly work because you can only travel "down and to the right".

The naive dynamic programming solution would essentially "work backwards" in a literal sense and start from the bottom-right and compute max score when starting at that cell.

Starting from the right-left, and from bottom-up, you can compute the best score you can get from that score simply. You do this for the m x n matrix, then you start from the top left and choose the direction that has the max score.

Upvotes: 1

Eamon Nerbonne
Eamon Nerbonne

Reputation: 48066

You don't need dynamic programming nor brute force for this!

To see why, let's analyze the rules:

  • You can move in direction j freely (left & right), so there's no reason to be careful about that direction - you can move into the optimial horizontal postion whenever you want.
  • Once you increase i (down) there's no way back (though you can increase i without gaining points). Each increase of i should net the maximal amount of points.
  • You gain points by leaving a cell, but you can only ever leave a row once.
  • That means you can subdivide this problem and do not need dynamic programming: you can move to the optimal j location, then take one diagonal step; repeat until done.
  • The optimal i step is moving from a non-last cell in a row with the highest value. You can't move from the last cell because there's no diagonal move possible - so if your matrix has only one column (or row for that matter) you'll never gain points. You can't lose points because the values are natural numbers (but if negative numbers were allowed, you can still skip a row).

In more detail, the optimal path is then found by...

  1. Does the matrix have just one column or row? Move right repeatedly without gaining points then end the program. You can't do much here.
  2. find the maximum value in the current row, ignoring the last value.
  3. generate 'j' moves towards a maximally-valued cell, then move diagonally.
  4. If you're not on the last row, go back to step 2.
  5. You're on the last row and cannot gain more points; just generate moves towards the bottom-right corner to finish your path.

That's it!

Note that there may be multiple maximal paths, your problem specification doesn't guarantee a unique solution.

EDIT: If you don't need the actual path, but just the numbers you scored, the algorithm is much easier - remove or disregard the last row and last column, then for each i (row) return the maximum value in that row.

Upvotes: 3

Related Questions