Maximum sum path in the matrix with a given starting point

Question

I am learning to tackle a similar type of dynamic programming problem to find a maximum path sum in a matrix.

I have based my learning on this algorithm on the website below.

Source: Maximum path sum in matrix

The problem I am trying to solve is a little bit different from the one on the website.

The algorithm from the website makes use of max() to update values in the matrix to find max values to create a max path.

For example, given an array:

sample = [[110, 111, 108, 1],
          [9, 8, 7, 2],
          [4, 5, 10, 300],
          [1, 2, 3, 4]]

The best sum path is 111 + 7 + 300 + 4 = 422

In the example above, the algorithm finds the first path by finding what is the max value of the first row of the matrix.

My question is, what if have to specify the starting point of the algorithm. The value h is given as the first element to start.

For example, given the sample array above, if h = 0, we need to start at sample[0][h], therefore the best path would be

110 (Our staring point) + 8 + 10 + 4 = 132

As you can see, the path can only travel downwards or adjacent, therefore if we start at h = 0, there will be values that we cannot reach some values such as 300.

Here is my messy attempt of solving this within the O(N*D) complexity,

# Find max path given h as a starting point
def find_max_path_w_start(mat, h):
    res = mat[0][0]
    M = len(mat[0])
    N = len((mat))

    for i in range(1, N):
        res = 0
        for j in range(M):
            # Compute the ajacent sum of the ajacent values from h
            if i == 1:
                # If h is starting area, then compute the sum, find the max
                if j == h:
                    # All possible
                    if (h > 0 and h < M - 1):
                        mat[1][h + 1] += mat[0][h]
                        mat[1][h] += mat[0][h]
                        mat[1][h - 1] += mat[0][h]
                        print(mat)
                    # Diagona Right not possible
                    elif (h > 0):
                        mat[1][h] += mat[0][h]
                        mat[1][h - 1] += mat[0][h]
                    # Diagonal left not possible
                    elif (h < M - 1):
                        mat[1][h] += mat[0][h]
                        mat[1][h + 1] += mat[0][h]
                # Ignore value that has been filled.
                elif j == h + 1 or j == h - 1 :
                    pass
                # Other elements that cannot reach, make it -1
                elif j > h + 1 or j < h - 1:
                    mat[i][j] = -1
            else:
                # Other elements that cannot reach, make it -1
                if j > h + 1 or j < h - 1:
                    mat[i][j] = -1
                else:
                    # When all paths are possible
                    if (j > 0 and j < M - 1):
                        mat[i][j] += max(mat[i - 1][j],
                                         max(mat[i - 1][j - 1],
                                             mat[i - 1][j + 1]))
                    # When diagonal right is not possible
                    elif (j > 0):
                        mat[i][j] += max(mat[i - 1][j],
                                         mat[i - 1][j - 1])
                    # When diagonal left is not possible
                    elif (j < M - 1):
                        mat[i][j] += max(mat[i - 1][j],
                                         mat[i - 1][j + 1])

            res = max(mat[i][j], res)

    return res

My approach is to only store the reachable values, if example if we start at h = 0, since we are starting at mat[0][h], we can only compute the sum of current and bottom max(mat[1][h] and sum of current and adjacent right mat[1][h + 1]), for other values I mark it as -1 to mark it as unreachable.

This doesn't return the expected sum at the end.

Is my logic incorrect? Are there other values that I need to store to complete this?

Answer 1

Here is a solution which works in a similar way to yours, however it only calculates path sums for at matrix values that could have started at h.

def find_max_path_w_start(mat, h):
    M = len(mat[0])
    N = len((mat))

    for i in range(1, N):
        # `h - i` is the left hand side of a triangle with `h` as the top point.
        # `max(..., 0)` ensures that is is at least 0 and in the matrix.
        min_j = max(h - i, 0)

        # similar to above, but the right hand side of the triangle.
        max_j = min(h + i, M - 1)

        for j in range(min_j, max_j + 1):
            # min_k and max_k are the start and end indices of the points in the above
            # layer which could potentially lead to a correct solution.
            # Generally, you want to iterate from `j - 1` up to `j + 1`,
            # however if at the edge of the triangle, do not take points from outside the triangle:
            # this leads to the `h - i + 1` and `h + i - 1`.
            # The `0` and `M - 1` prevent values outside the matrix being sampled.
            min_k = max(j - 1, h - i + 1, 0)
            max_k = min(j + 1, h + i - 1, M - 1)

            # Find the max of the possible path totals
            mat[i][j] += max(mat[i - 1][k] for k in range(min_k, max_k + 1))
            
    # Only sample from items in the bottom row which could be paths from `h`
    return max(mat[-1][max(h - N, 0):min(h + N, M - 1) + 1])


sample = [[110, 111, 108, 1],
          [9, 8, 7, 2],
          [4, 5, 10, 300],
          [1, 2, 3, 4]]

print(find_max_path_w_start(sample, 0))

Answer 2

You can set all elements of the first row except h to negative infinity, and compute the answer as if there is no starting point restriction.

For example, put this piece of code at the start of your code

for i in range(M):
    if i != h:
        mat[0][i] = -1e100

Answer 3

It's easy to build a bottom up solution here. Start thinking the case when there's only one or two rows, and extend it to understand this algorithm easily.
Note: this modifies the original matrix instead of creating a new one. If you need to run the function multiple times on the same matrix, you'll need to create a copy of the matrix to do the same.

def find_max_path_w_start(mat, h):
    res = mat[0][0]
    M = len(mat[0])
    N = len((mat))

    # build solution bottom up
    for i in range(N-2,-1,-1):
        for j in range(M):
            possible_values = [mat[i+1][j]]
            if j==0:
                possible_values.append(mat[i+1][j+1])
            elif j==M-1:
                possible_values.append(mat[i+1][j-1])
            else:
                possible_values.append(mat[i+1][j+1])
                possible_values.append(mat[i+1][j-1])
            mat[i][j] += max(possible_values)
    return mat[0][h]

sample = [[110, 111, 108, 1],
          [9, 8, 7, 2],
          [4, 5, 10, 300],
          [1, 2, 3, 4]]

print(find_max_path_w_start(sample, 0)) # prints 132