Нахождение маршрута с наибольшей ценностью

Question

Учитывая приведенные ниже данные, найдите маршрут с наибольшим значением, перемещающийся снизу слева в верхний правый угол.

[{ 0, 0, 0, 6 }, 
  { 2, 0, 0, 2 }, 
  { 0, 1, 1, 1 }, 
  { 3, 0, 0, 0 }]

go can only move right (east) or up (north)
Highest value route here is 3 -> 0 -> 1 -> 1 -> 1 -> 2 ->6 = 14

Как мне подойти к этой проблеме.Является ли мой подход ниже в качестве псевдокода правильным?

max = 0
array = defined_array 
i = len(array)
k = 0  
def path(i,j):
total = 0
    for j in range(4):
        k = j;
        total = total + int(array[i][j])    
        if total > max:
            max = total
    return path(--i,k)

key= 3
def path(i,j):
    for i in range(i):
        for j in range(array[i]):
            total = total + array[i][j]

Answer 1

Я вообще не получил ваш подход.
Это проблема простого динамического программирования.
Рассмотрим это как двумерный массив Arr [4] [4]

[{ 0, 0, 0, 6 }, 
  { 2, 0, 0, 2 }, 
  { 0, 1, 1, 1 }, 
  { 3, 0, 0, 0 }]

Создайте еще один массив dp из 4 * 4

Первое, что вам нужно, это инициализировать базовые случаи.
Итак, первый столбец и последняя строка - это наш базовый случай.
dp[0][3]=Arr[0][3];

После этого для первого столбца
dp[i][0]=dp[i+1][0]+Arr[i][0];

Для последнего ряда
dp[3][i]=dp[3][i-1]+Arr[3][i];

Для других значений
dp[i][j]=max(dp[i][j-1],dp[i+1][j])+Arr[i][j];
Мы выберем максимальное значение.

Наш массив dp будет выглядеть так, где ответ будет 14

[{ 5, 5, 5, 14 }, 
  { 5, 5, 5, 8 }, 
  { 3, 4, 5, 6 }, 
  { 3, 3, 3, 3 }]

Answer 2

Это в основном проблема поиска оптимального пути (в данном случае: маршрута с наибольшим значением) через график.

Существуют хорошо известные методы поиска кратчайших путей, такие как алгоритм Дейкстры и алгоритм Беллмана-Форда .

Для вашего графика, являющегося направленным и ациклическим («DAG»), я обнаружил два обсуждения здесь и здесь о том, что эти алгоритмы не могут быть просто «обращены» изот минимума до максимума, чтобы найти самый длинный путь, но он работает, если вы преобразуете свой график, инвертируя каждый вес (значение) в его отрицательное число.

См. Также Статья в Википедии о проблеме самого длинного пути .