How to maximize the value of the path?

Question

We are given a N*N grid. And we are at the top left corner of the grid initially. Every square of the grid has some value attached to it, that is if someone reaches that square he wins the amount of money in dollars equal to the value attached to the square. Now legal moves are one step towards the right or one step towards the bottom. We have to reach the bottom right corner of the grid in a path such that we can maximize the amount of money won. Obviously we have to stay within the grid and cannot wander off it. I started this problem by a greedy approach that at each step we look at the immediate right square and immediate square below the occupied square, and at each step choose the square having the higher value. But this does not give the right result all the time. For example in the following grid,

{  6,   9,  18,   1 }
{  2,  10,   0,   2 }
{  1, 100,   1,   1 }
{  1,   1,   1,   1 }

here my algorithm gives the maximum valued path as

6 -> 9 -> 18 -> 1 -> 2 -> 1 -> 1

which totals to 37, but we could have earned more on the path

6 -> 9 -> 10 -> 100 -> 1 -> 1 -> 1

which totals to 128. Could you people please help me in building a suitable algorithm? I have not yet coded this one because it would give a wrong output anyway. I don't know how to cope with this problem without brute force which would consist of seeing the values in all the paths not containing the square with the minimum value, and then finding the maximum.

#include <iostream>
#include <queue>
using namespace std;
int main()
{ int n; cin >> n;
int a[n+1][n+1], b[n+1][n+1];
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
    cin >> a[i][j]; b[i][j]=a[i][j];
}
}

queue <int> q; int u,v,m=0;
q.push(0);q.push(0);
while (q.size()!=0)
{
    u=q.front(); q.pop(); v=q.front(); q.pop();
    if (v<n-1)
    {
        m=b[u][v]+a[u][v+1];
        if (m>b[u][v+1])
        {  b[u][v+1]=m; }
        q.push(u);q.push(v+1);
    }
    if (u<n-1)
    {
        m=b[u][v]+a[u+1][v];
        if (m>b[u+1][v])
        { b[u+1][v]=m; }
        q.push(u+1);q.push(v);
    }
}
cout << b[n-1][n-1];
return 0;
}

Answer 1

The problem can be solved with the following approach. Each cell at position (i,j) gets associated with a value val(i,j) which is the maximum total value possible by reaching it with the described legal moves (to the bottom, to the right) starting at position (0,0). The value at position (0,0) is the value from the grid, in the sequel termed as grid(i,j) for every i, j in {0,...,N-1}. We obtain the follwing recurrence relation

val(i,j) = grid(i,j) + max{ val(i-1,j), // path coming from upper cell
                            val(i,j-1)  // path coming from left cell
                          }

where we suppose that indices outside of {0,...,N-1} * {0,...N-1} yield a value of negative infinity and are never really used. The recurrence relation is valid as there are at most two cases to reach a cell, namely from its upper neighbor or its left neighbour (except for cells at the border, which perhaps may be reached from only one neighbour).

The key point for an efficient evaluation of val is to organize the calculation of values in a sequence such that all needed neighbors are already evaluated; this can be done by succesively staring calculation at the leftmost cell for which val is not yet calculated and working from there in an upwards-rightwards manner until the top row is reached. This is iterated until position val(N-1,N-1) is evaluated, which yields the desired result.

If in addition the specific path to (N-1,N-1) is demanded, either backtracking or some auxiliary data structure has to be used to store how the value in the above recurrence relation was calculated, i.e. which term yields the maximum.

Edit

Alternatively, the evaluation can be done row-wise from left to right, which also has the desired property that all necessary values for the recurrence relation are already calculated; this is apparently easier to implement. In either case, the runtime bound will be O(n^2).

Answer 2

Actually this is a problem which is solvable using dynamic programming. You only need to adapt the algorithm for calculating the edit distance allowing for varying rewards. The algorithm is described for example in https://web.stanford.edu/class/cs124/lec/med.pdf

The basic idea is that you start from top and you fill a square whenever you now its neighbouring (top,left) field. The value you put in the field is the value of the higher of the two neighbours and the value of the current field. When you reach bottom right you just have to follow the path back.