maximum matrix cost path,

Question

I am trying to solve this problem through dynamic programming:

You are given a matrix of n rows and m columns. Every element has a number and the rabbit staying at the top left element.

Calculate the maximum sum such that the rabbit gets to the bottom element and only two moved allowed:

Two steps right and 1 step down (x+2, y+1);
Two steps down and 1 step to the right (x+1, y+2);

Input:

The first line contains two naturals n and m (1 ≤ n, m ≤ 10³) – the quantity of rows and columns of the matrix.

The next n lines contain m numbers – the values of the matrix elements.

The top left coordinates are (1, 1), the bottom right corner’s – (n, m).

Output:

The maximum sum so that the rabbit reaches the bottom right. If bottom right can not be reached, output -

Input 1:

3 3 
5 0 0 
0 1 2  
1 0 1 

Output 1:

-

Input 2:

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

Output 2:

13

This the code I tried to develop:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>

using namespace std;
void findMaxSum(int *a[], int r, int c)
{
    int **res = new int*[r];
    for (int i = 0; i < r; i++) {
        res[i] = new int[c];
        for (int j = 0; j < c; j++)
            res[i][j] = -1;
    }
    for (int i = 0; i < r-1; i++) {
        for (int j = i; j < c-1; j++) {
            res[i + 1][j + 2] = max(a[i][j] + a[i + 1][j + 2], res[i + 1][j + 2]);
            res[i + 2][j + 1] = max(a[i][j] + a[i + 2][j + 1], res[i + 2][j + 1]);
        }
    }
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++)
            cout << res[i][j] << " ";
        cout << endl;
    }
    delete[] res;
}

int main() {    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int r, c;
    cin >> r >> c;
    int **a = new int*[r];
    for (int i = 0; i < r; i++) {
        a[i] = new int[c];
    }
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++)
            cin >> a[i][j];
    }
    findMaxSum(a, r, c);
    delete[] a;
    return 0;
}

Is this the approach, are the calculations inside for loops correct?

Answer 1

First realise that this is a variant of the more common problem where valid "moves" are "right" and "down". It can be mapped to it.

If you visualise the spots that can be reached by valid moves, you get this pattern in the matrix:

x - - - - - - - -
- - x - - - - - - 
- x - - x - - - -
- - - x - - x - -
- - x - - x - - x
- - - - x - - x -
- - - x - - x - -
- - - - - x - - x

So actually many matrix values don't even play a role -- they cannot be reached. If we also remove the spots from where the target cannot be reached, then we get this. I also use some different letters to highlight a property:

x - - - - - - - -
- - x - - - - - - 
- y - - x - - - -
- - - y - - x - -
- - z - - y - - -
- - - - z - - y -
- - - - - - z - -
- - - - - - - - z

Where it has an "x", the spot can be reached via (+2,+1) type of moves only. Where it has an "y", it needs one (+1,+2) type of move, and where there is a "z", two of those are needed.

This is a shape that can be translated to this shape:

x x x x
y y y y 
z z z z

It would be interesting to translate the problem like that, and solve it in that configuration.

I will not pursue that idea here.

Your code is currently missing the test for when to output -.

We need to test whether the target cell can be reached. You can see that a spot cannot be reached if the sum of its x and y coordinate (when zero-based) is not a multiple of 3. And there are also spots where this sum is a multiple of 3, but which are still out of reach. This is where one of the coordinates is at least the double of the other coordinate (marked with an asterisk):

x - - * - - * - -
- - x - - * - - * 
- y - - x - - * -
* - - y - - x - -
- - z - - y - - -
- * - - z - - y -
* - - - - - z - -
- - * - - - - - z

So you should add this line to your code:

if ((r+c) % 3 != 2 || r*2 < c || c*2 < r) {
    cout << "-";
    return;
}

(r+c) % 3 != 2 is derived from (r-1 + c-1) % 3 != 0, and r*2 < c is derived from (r-1)*2 < (c-1)*2 with a difference of 1, which is not relevant given the first condition.

For the initialisation part: it is not necessary to initialise the res matrix with -1 values. You wouldn't want to involve a -1 in your calculation anyway. You'll want to avoid relying on such values. Instead you must initialise a starting point for the dynamic programming to work:

res[0][0] = a[0][0];

Then, for the actual "bootstrapping": I would first move with only one type of move, and accumulate the cost in that direction:

for (int i = 2, j = 1; (r-i)*2 > c-j; i+=2, j++) {
    res[i][j] = res[i-2][j-1] + a[i][j];
}

Note that the loop's stop-condition eliminates spots from where the target would be out of reach.

Do the same in the other direction:

for (int i = 1, j = 2; (c-j)*2 > r-i; i++, j+=2) {
    res[i][j] = res[i-1][j-2] + a[i][j];
}

Now you have set up the "outer borders" for the main dynamic programming part. The other valid spots will always have 2 possible spots to come from. So take all other paths by choosing the maximum value from the two spots you could come from:

for (int i = 2, j = 1; (r-i)*2 > c-j; i+=2, j++) {
    for (int m = i + 1, n = j + 2; (c-n)*2 > r-m; m++, n += 2) {
        res[m][n] = max(res[m-1][n-2], res[m-2][n-1]) + a[m][n];
    }
}

And finally output the result:

cout << res[r-1][c-1];

NB: I would prefer a function to return that value, and let main do all the I/O.

Answer 2

Here are the points to address:

• Out-of-bounds access for array elements. Look carefully at which elements you want to access, and what are the loop boundaries. The simplest fix is to widen the arrays accordingly.

• Wrong initialization for array elements. Note that -1 (an unreachable square) plus 10 is 9 which looks like a valid value. The simplest fix is to initialize with minus-infinity (which is the proper neutral element for the max operation) instead of -1. A good default value for minus-infinity is INT_MIN / 2.

These two might be sufficient to make the program work.

---

Here are the points to consider for the future:

• Array construction. For one, there are not enough delete operations for the corresponding new operation, so the program leaks memory. Having said that, I don't see why would one need the cumbersome memory management of multidimensional plain arrays in C++, when vectors do the same with more convenience. The minor slowdown associated with vectors does not justify suffering from whole classes of bugs in the other 97% of the cases.

• Asking questions. The question goes like this: "here is the problem, and here is the solution in code". The missing step is explaining, in text, what the code is meant to do. As a result, people not familiar with the problem and the solution will have a hard time actually understanding your question in the first place, and rightfully consider it a question not in proper form. Additionally, you may find that addressing that missing step, while looking at your code of course, will answer some questions without any more interaction :) (see Rubber duck debugging).