Find the least and most weighted path in a matrix

Question

I tried to work on using the most effiency way to find the least and most weight path traverse across the matrix from [min(m), min(n)] to [max(m), max(n)], when an step is choosen [m,n], the next step should be [m+i, n+j].

+---+----+---+---+---+---+----+
| 1 | 0  | 5 | 2 | 5 | 4 | 10 |
+---+----+---+---+---+---+----+
| 2 | 3  | 2 | 5 | 0 | 0 | 1  |
+---+----+---+---+---+---+----+
| 1 | 3  | 5 | 1 | 4 | 1 | 1  |
+---+----+---+---+---+---+----+
| 0 | 0  | 0 | 1 | 2 | 3 | 5  |
+---+----+---+---+---+---+----+
| 2 | 3  | 4 | 2 | 3 | 1 | 1  |
+---+----+---+---+---+---+----+
| 0 | 10 | 1 | 2 | 2 | 3 | 10 |
+---+----+---+---+---+---+----+

Here a generated matrix, what algorithm should i use or any suggestion on how should i proceed? Thanks in advance.

Edit: Thanks for the helps, but i find it strange when i throw in the test case below:

+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+
| 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+
| 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+

In the above test case, the cost of expected maximum weight path is 1.

As i like to apologies for not mentioning in the thread, i and j must be >=1, so the next step should not be on the same column or same row.

Answer 1

The problem can be solved using a dynamic programming approach. A correct solution is achieved even if there are negatives values at the given matrix.

Definitions and considerations:
Array indexing starts at 0.
A -> Input matrix (n rows and m columns)
DP -> Matrix used to store calculated values
A move from (x, y) to (x + a, y + b) is valid if x ≤ x + a < n and y ≤ y + b < m and 0 < a + b.

DP[i][j] store the cost of minimum cost path that starts at (0, 0) and ends at (i, j). Answer to the problem is found at DP[n - 1][m - 1] after calculations.

Define recurrence relation:

To avoid the O(n²) loop in the calculation of DP[i][j] we use an auxiliary matrix MN where:

You can prove the equality by yourself.

Code:

for(int i = 0; i < n; ++i)
    for(int j = 0; j < m; ++j)
    {
        if(i == 0 && j == 0)
            MN[i][j] = DP[i][j] = A[i][j];
        else if(i == 0 && 0 < j)
        {
            DP[i][j] = MN[i][j - 1] + A[i][j];
            MN[i][j] = min(MN[i][j - 1], DP[i][j]);
        }
        else if(0 < i && j == 0)
        {
            DP[i][j] = MN[i - 1][j] + A[i][j];
            MN[i][j] = min(MN[i - 1][j], DP[i][j]);
        }
        else
        {
            DP[i][j] = min(MN[i - 1][j], MN[i][j - 1]) + A[i][j];
            MN[i][j] = min({MN[i - 1][j], MN[i][j - 1], DP[i][j]});
        }
    }

Time Complexity:
There are n*m elements and we do a constant time operation on each of them then algorithm's running time is O(n*m).

Note: To solve maximum cost path just use max instead of min operations.

Answer 2

This can be solved with dynamic programming since there is no negative value on the matrix.

As Henry said, there is no point on finding min value path(which will be just direct path to max(m), max(n)).

This code would find the Max value.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> arr;
    arr.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        arr[i].resize(m + 1);
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }

    for (int i = n; i >= 1; i--) {
        for (int j = m; j >= 1; j--) {
            int maxval;
            if (i == n && j == m) continue;
            else if (i == n) {
                maxval = arr[i][j + 1];
            }
            else if(j == m) {
                maxval = arr[i + 1][j];
            }
            else {
                maxval = arr[i + 1][j] > arr[i][j + 1] ? arr[i + 1][j] : arr[i][j + 1];
            }           
            arr[i][j] += maxval;
        }
    }

    cout << arr[1][1];
    
    return 0;
}
//test case
//6 7
//1 0 5 2 5 4 10 
//2 3 2 5 0 0 1  
//1 3 5 1 4 1 1  
//0 0 0 1 2 3 5 
//2 3 4 2 3 1 1 
//0 10 1 2 2 3 10 
//answer : 45