Maximum cost of traversal in matrix using dynamic programming

Question

Suppose I've a m x n matrix in Java.

I want to find the maximum traversal cost from first column to last column. Each value represents the cost incurred. I'm allowed to travel in up, down and right directions across the matrix. Each cell can be visited only once. Transitions are allowed from a top cell of a column to the bottom of the same and vice-versa.

For simplicity, consider the following matrix:

2 3 17
4 1 -1
5 0 14

If I'm supposed to find the maximum cost, my answer would be 46 (2 → 5 → 4 → 1 → 3 → 0 → 14 → 17).

I've tried to solve this problem using dynamic approach using the following recursive relation:

maxCost(of destination node) = max{ maxCost(at neighbouring node 1), maxCost(at neighbouring node 2), maxCost(at neighbouring node 3) } + cost(of destination node)

In this case, it would be something like:

maxCost(17) = max{ maxCost(3), maxCost(-1), maxCost(14) } + 17;

Since, each cell is allowed to be visited only once, I understand that I would need to maintain a corresponding m x n isVisited matrix. However, I can't figure out how to maintain isVisited matrix. The matrix would be modified when maxCost(3) is calculated; but for maxCost(-1) and maxCost(14), I would require its initial status (which would be lost).

Is my approach correct for this problem? Also, I can't figure out how should my functions look like. (This is my first attempt at dynamic programming).

Answer 1

This is a nice and slightly tricky problem. For a DP solution, we must phrase it in a way that comports with the principle of optimality.

This requires us to define a "state" so that the problem can be written in terms of an n-way decision that takes us to a new state that, in turn, is a new, smaller version of the same problem.

A suitable choice for state is the current position of the traversal plus a signed integer f that says where and how many untraversed (I'll call them "free") rows there are in the current column. We can write this as a triple [i,j,f].

The value of f tells us whether it's okay to move up and/or down. (Unless we're in the right column, it's always possible to move right, and it's never possible to move left.) If f is negative, there are f free rows "above" the current position, which may wrap around to the matrix bottom. If positive, there are f free rows below. Note that f=m-1 and f=1-m mean the same thing: all rows are free except the current position's. For simplicity, we'll use f==m-1 to represent that case.

The single integer f is all we need to describe free spaces because we can only only traverse in steps of size 1, and we never move left. Ergo there can't be non-contiguous groups of free spaces in the same column.

Now the DP "decision" is a 4-way choice:

1. Stand pat at the current square: only valid in the last column.
2. Move up: only valid if there's free space above.
3. Move down: only valid if there's free space below.
4. Move right: valid except in the last column.

Let, C(t) be the max cost function in the DP, where t is a triple [i,j,f]. Then the max cost we can achieve is the cost A[i,j] from the matrix added to the cost of the rest of the traversal after making the optimum decision 1 to 4 above. The optimum decision is just the one that produces the highest cost!

All this makes C the max of a set where all the elements are conditional.

C[i,j,f] = max { A[i,j] if j==n-1, // the "stand pat" case
               { A[i,j]+C[i,j+1,m-1] if j<n-1  // move right
               { A[i,j]+C[i+1,j,f-1] if f>0    // move down
               { A[i,j]+C[i-1,j,2-m] if f==m-1 // first move in col is up
               { A[i,j]+C[i-1,j,f+1] if f<0    // other moves up

Sometimes words are clearer than algebra. The "down" case would be...

One potential max path cost from position [i,j] to the goal (right column) is the matrix value A[i,j] plus the max cost obtainable by moving down to position [i+1,j]. But we can move down only if there are free spaces there (f>0). After moving down, there's one less of those (f-1).

This explains why the recursive expression is C[i+1,j,f-1]. The other cases are just variations of this.

Also note that the "base cases" are implicit above. In all states where f=0 and j=n-1, you have them. The recursion must stop.

To get the final answer, you must consider the max over all valid starting positions, which are the first column elements, and with all other elements in the column free: max C[i,0,m-1] for i=0..m-1.

Since you were unsuccessful with finding a DP, here is a table-building code to show it works. The dependencies in the DP require care in picking the evaluation order. Of course the f parameter can be negative, and the row parameter wraps. I took care of these in 2 functions that adjust f and i. Storage is O(m^2):

import java.util.Arrays;

public class MaxPath {
  public static void main(String[] args) {
    int[][] a = {
      {2, 3, 17},
      {4, 1, -1},
      {5, 0, 14}
    };
    System.out.println(new Dp(a).cost());
  }
}

class Dp {
  final int[][] a, c;
  final int m, n;

  Dp(int[][] a) {
    this.a = a;
    this.m = a.length;
    this.n = a[0].length;
    this.c = new int[2 * m - 2][m];
  }

  int cost() {
    Arrays.fill(c[fx(m - 1)], 0);
    for (int j = n - 1; j >= 0; j--) {
      // f = 0
      for (int i = 0; i < m; i++) {
        c[fx(0)][i] = a[i][j] + c[fx(m - 1)][i];
      }
      for (int f = 1; f < m - 1; f++) {
        for (int i = 0; i < m; i++) {
          c[fx(-f)][i] = max(c[fx(0)][i], a[i][j] + c[fx(1 - f)][ix(i - 1)]);
          c[fx(+f)][i] = max(c[fx(0)][i], a[i][j] + c[fx(f - 1)][ix(i + 1)]);
        }
      }
      // f = m-1
      for (int i = 0; i < m; i++) {
        c[fx(m - 1)][i] = max(c[fx(0)][i], 
            a[i][j] + c[fx(m - 2)][ix(i + 1)], 
            a[i][j] + c[fx(2 - m)][ix(i - 1)]);
      }
      System.out.println("j=" + j + ": " + Arrays.deepToString(c));
    }
    return max(c[fx(m - 1)]);
  }
  // Functions to account for negative f and wrapping of i indices of c.
  int ix(int i) { return (i + m) % m; }
  int fx(int f) { return f + m - 2; }
  static int max(int ... x) { return Arrays.stream(x).max().getAsInt(); }
}

Here's the output. If you understand the DP, you can see it building optimal paths backward from column j=2 to j=0. The matrices are indexed by f=-1,0,1,2 and i=0,1,2.

j=2: [[31, 16, 14], [17, -1, 14], [17, 13, 31], [31, 30, 31]]
j=1: [[34, 35, 31], [34, 31, 31], [34, 32, 34], [35, 35, 35]]
j=0: [[42, 41, 44], [37, 39, 40], [41, 44, 42], [46, 46, 46]]
46

The result shows (j=0, column f=m-1=2) that all elements if the first column are equally good as starting points.

Answer 2

It's a tough one. Notice that since your path cannot repeat visited cells your possible paths would have 'snake'-like behavior such as:

The idea is to store in f[j][i] the maximum length of paths that end at the cell (j, i). Lets say now that we want to transition from f[j][i-1] to f[j'][i]. We can, then, either choose to go from cell (j, i) to cell (j', i) directly or we could go from cell (j, i) to cell (j', i) by wrapping around the top/botton edge. So the update for f[j][i], then, could be calculated as:

where

Here a is the given array.

The problem now is how to calculate sum(a[j..j'][i] effectively since otherwise the runtime would be O(m^3n). You can solve this by using a temporary variable tmp_sum for the sum(a[j..j'][i]) which you increment as you increment j. The runitme of algorithm then would be O(m^2 n).

Here is an sample implementation:

package stackoverflow;

public class Solver {

    int m, n;
    int[][] a, f;

    public Solver(int[][] a) {
        this.m = a.length;
        this.n = a[0].length;
        this.a = a;
    }

    void solve(int row) {
        f = new int[m][n];
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                f[i][j] = Integer.MIN_VALUE;

        for (int i = 0; i < n; ++i) {
            int sum = 0;
            for (int j = 0; j < m; ++j)
                sum += a[j][i];
            for (int j1 = 0; j1 < m; ++j1) {
                int tmp_sum = 0;
                boolean first = true;
                for (int j2 = j1; j2 != j1 || first; j2 = (j2+1)%m) {
                    if (first)
                        first = false;
                    tmp_sum += a[j2][i];
                    int best_sum = Math.max(tmp_sum, sum - tmp_sum +a[j1][i]+a[j2][i]);
                    if (j1 == j2)
                        best_sum = a[j1][i];
                    int prev = 0;
                    if (i > 0)
                        prev = f[j1][i-1];
                    f[j2][i] = Math.max(f[j2][i], best_sum + prev);
                }
            }
        }

        System.out.println(f[row][n-1]);
    }

    public static void main(String[] args) {
        new Solver(new int[][]{{2, 3, 17}, {4, 1, -1}, {5, 0, 14}}).solve(0); //46
        new Solver(new int[][]{{1, 1}, {-1, -1}}).solve(0); //2
    }
}

Answer 3

Thank you everyone for your contributions.

I've come up with a solution using recursive technique using system stack. I think that my solution is relatively easier to understand.

Here's my code:

import java.util.Scanner;

public class MatrixTraversal {

    static int[][] cost;
    static int m, n, maxCost = 0;

    public static void solve(int currRow, int currCol, int[][] isVisited, int currCost) {

        int upperRow, lowerRow, rightCol;
        isVisited[currRow][currCol] = 1;

        currCost += cost[currRow][currCol];             //total cost upto current position

        if( currCol == (n - 1)                          //if we have reached the last column in matrix
            && maxCost < currCost )                     //and present cost is greater than previous maximum cost
            maxCost = currCost;

        upperRow = ((currRow - 1) + m) % m;             //upper row value taking care of teleportation
        lowerRow = (currRow + 1) % m;                   //lower row value taking care of teleportation
        rightCol = currCol + 1;                         //right column value

        if( isVisited[upperRow][currCol] == 0 )     //if upper cell has not been visited
            solve(upperRow, currCol, isVisited, currCost);

        if( isVisited[lowerRow][currCol] == 0 )     //if lower cell has not been visited
            solve(lowerRow, currCol, isVisited, currCost);

        if( rightCol != n &&                            //if we are not at the last column of the matrix
            isVisited[currRow][rightCol] == 0 )     //and the right cell has not been visited
            solve(currRow, rightCol, isVisited, currCost);

        isVisited[currRow][currCol] = 0;

    }

    public static void main(String[] args) {

        int[][] isVisited;
        int i, j;

        Scanner sc = new Scanner(System.in);

        System.out.print("Enter the no.of rows(m): ");
        m = sc.nextInt();

        System.out.print("Enter the no.of columns(n): ");
        n = sc.nextInt();

        cost = new int[m][n];
        isVisited = new int[m][n];

        System.out.println("Enter the cost matrix:");
        for(i = 0; i < m; i++)
            for(j = 0; j < n; j++)
                cost[i][j] = sc.nextInt();              //generating the cost matrix

        for(i = 0; i < m; i++)
            solve(i, 0, isVisited, 0);                  //finding maximum traversal cost starting from each cell in 1st column 

        System.out.println(maxCost);

    }

}

However, I'm not sure whether this is the best and the fastest way to compute the solution.

Please let me know your views. I'll accept this as answer accordingly.

Answer 4

One possible optimization is that we only need to calculate different options (other than a full sum) for columns with negative numbers or sequences of non-negative columns less than m in length, enclosed by columns with negatives. We need one column and a (conceptual) matrix to compute the max for a sequence of such columns; a matrix for the current column that converts into a column of maximums for each exit point. Each matrix represents the maximum sum for entry at y and exit at y' combined with the previous max just preceding the entry point (there are two possibilities for each, depending on the path direction). The matrix is symmetrically reflected along the diagonal (meaning sum entry...exit = sum exit...entry) until the various previous maximums for each entry point are added.

Adding an additional column with negative numbers to the example, we can see how the cummulative sums may be applied:

2  3  17  -3
4  1  -1  15
5  0  14  -2

(We'll ignore the first two non-negative columns for now and add 15 later.)

Third column:

 y' 0  1  2
y 
0   17 30 31
1   30 -1 30
2   31 30 14

For the fourth column matrix, each entry point needs to be combined with the maximum for the same exit point from the previous column. For example, entry point 0 is added with max(17,30,31):

 y' 0  1  2
y 
0   -3 12 10  + max(17,30,31)
1   12 15 13  + max(30,-1,30)
2   10 13 -2  + max(31,30,14)

       =

    28 43 41
    42 45 43
    41 44 29

We can see the final max has (entry,exit) (1,1) and solution:

15 + (0,1) or (2,1) + (1,1)