Java – Maximum traversal cost in matrix using dynamic programming

Suppose I have an M x n matrix in Java

I want to find the maximum traversal cost from the first column to the last column Each value represents the cost incurred I was allowed to move up, down and right along the matrix Each cell can only be accessed once Allow conversion from the top cell of the column to the bottom, and vice versa

For simplicity, consider the following matrix:

2 3 17
4 1 -1
5 0 14

If I should find the maximum cost, my answer is 46 (2 → 5 → 4 → 1 → 3 → 0 → 14 → 17)

I have tried to solve this problem using dynamic methods using the following recursive relationships:

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 will look like:

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

Because each cell is allowed to be accessed once, I understand that I need to maintain a corresponding M × N isvisiting matrix However, I do not know how to maintain the isvisiting matrix When maxcost (3) is calculated, the matrix will be modified; But for maxcost (- 1) and maxcost (14), I will need their initial state (which will be lost)

Is my method correct for this problem? Besides, I don't know what my function should be This is my first attempt at dynamic programming

Solution

This is a difficult one Note that since your path cannot access cells repeatedly, your possible path will have "snake" behavior, for example:

The idea is to store the maximum length of the path ending on cell (J, I) in F [J] [i] Now let's say we're going to switch from F [J] [I-1] to f [J '] [i] Then we can directly select from cell (J, I) to cell (J ', I), or we can select from the edge of cell (J, I). Therefore, the update of F [J] [i] can be calculated as:

where?

Here a is the given array

The problem now is how to effectively calculate sum (a [J.. J '] [i], otherwise the runtime will be o (m ^ 3n). You can use the temporary variable TMP_ Sum to solve (a [J.J '] [i]). When you increase J, you will increase The operator of the algorithm will be o (m ^ 2 n)

The following is an example 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,14}}).solve(0); //46
        new Solver(new int[][]{{1,1},{-1,-1}}).solve(0); //2
    }
}