Maximum cost path in integer matrix

Question

In preparation for my design and algorithms exam, I encountered the following problem.

Given a $2 \times N$ integer matrix $(a[i][j] \in [-1000, 1000])$ and an unsigned integer $k$, find the maximum cost path from the top left corner $(a[1][1])$ and the bottom right corner $a[2][N]$, given the following:

---

$\bullet$ The path may not go through the same element more than once

$\bullet$ You can move from one cell to the other vertically or horizontally

$\bullet$ The path may not contain more than $k$ consecutive elements from the same line

$\bullet$ The cost of the path is determined by the sum of all the values stored within the cells it passes through

---

I've been thinking of a simple greedy approach that seems to work for the test cases I've tried, but I'm not sure if it's always optimal. Namely, while traversing the matrix, I select a the maximum cost cell on the vertical or horizontal and then go from there. I've got a counter I only increment if the current cell is on the same line with the previously examined one and reset it otherwise. If at some point the selected element happens to be one that makes the counter go over the given value of $k$, I simply go with the other option that's left.

However, I feel that I'm missing out on something terribly important here, but I just can't see what. Is there some known algorithm or approach that may be used here?

Also, the problem asks for an optimal solution (regarding temporal complexity).

Answer 1

This problem was basically made for dynamic programming (DP). Just review it and follow a couple of examples and solving this problem is straight-forward.

Your simple greedy approach does not always work. Consider:

[ begin ] [  2 ]
[ 3 ]     [ 10 ]
[ 1 ]     [ -1000 ]
[ 1 ]     [ end ]

The optimal solution would be to go right, down, left, down, down, right.

Answer 2

We shall approach this using dynamic programming -- the greedy algorithm is 'myopic' in that it only considers immediate neighbors and not the path that follows those neighbors.

Let $C(i, \ j, \ m)$ be the cost of the max-cost path starting from $a[i][j]$ going towards $a[2][n]$, where $i$ is either $1$ or $2$, $\ j \in [1, n]$ and $m \in [0, k]$.

• $m$ here denotes that we have $m$ remaining consecutive steps that could be taken along row $i$.
• The additional constraint we enforce here is that when we are calculating $a[1][i]$, we have not yet visited $a[2][i]$, and similarly when we're calculating $a[2][i]$, we have not yet visited $a[1][i]$.

With this constraint in place, what recurrence can we come up with? Well,

1. $C(1, \ j, \ m) = a[1][j] + \max \{ M(1, j+1, m-1), \ a[2][j] + M(2, j+1, k)\} \ $ and similarly,
2. $C(2, \ j, \ m) = a[2][j] + \max \{ M(2, j+1, m-1), \ a[1][j] + M(1, j+1, k)\} \ $

Now, what's the rationale here? If we started at $a[1][j]$, we have two choices:

• continue along row $1$ : we then go to $a[1][j+1]$ with $m-1$ remaining consecutive steps that we can take along row $1$. (note here that $a[2][j+1]$ is not yet visited, maintaining the invariant).

• switch to row $2$ : we go to $a[2][j]$, incurring a cost of $a[2][j]$, and then have only one choice from there - to go to $a[1][j+1]$. Because we have switched rows, we can now refresh our count and take $k$ consecutive steps along row $2$. (note again that we haven't visited $a[1][j+1]$ yet).

Now if we calculate our subproblems starting from $j = n$ towards $j=1$ for every value of $m$, you shall have your answer in $C(1, \ 1, \ k)$.

I shall leave the base cases and runtime analysis to you. Note that my solution calculates the cost of the path and not the path itself; can you extend my solution to calculate the path too?