Максимальный суммарный путь в матрице с заданной начальной точкой

Я учусь решать аналогичные задачи динамического программирования, чтобы найти максимальную сумму путей в матрице.

Я основал свое обучение на этом алгоритме на веб-сайте ниже.

Источник: Максимальная сумма путей в матрице

Проблема, которую я пытаюсь решить, немного отличается от той, что описана на сайте.

Алгоритм с веб-сайта использует max() для обновления значений в матрице, чтобы найти максимальные значения для создания максимального пути.

Например, для массива:

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

Путь наилучшей суммы: 111 + 7 + 300 + 4 = 422

В приведенном выше примере алгоритм находит первый путь, определяя максимальное значение первой строки матрицы.

У меня вопрос, а что, если нужно указать начальную точку алгоритма. Значение h задается как первый элемент для запуска.

Например, учитывая приведенный выше образец массива, если h = 0, нам нужно начать с образца [0] [h], поэтому лучшим путем будет

110 (наша исходная точка) + 8 + 10 + 4 = 132

Как видите, путь может идти только вниз или рядом, поэтому, если мы начнем с h = 0, будут значения, которых мы не сможем достичь, например, 300.

Вот моя грязная попытка решить это в рамках сложности O (N * D),

# 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

Мой подход состоит в том, чтобы хранить только достижимые значения, например, если мы начинаем с h = 0, поскольку мы начинаем с mat[0][h], мы можем вычислить только сумму текущего и минимального max(mat[1][h] и суммы текущего и смежного справа mat[1][h + 1]), для других значений я помечу его как -1, чтобы пометить его как недоступный.

Это не возвращает ожидаемую сумму в конце.

Моя логика неверна? Есть ли другие значения, которые мне нужно сохранить, чтобы завершить это?