Для динамического программирования вам нужны граничные условия и способ оценить, где вы находитесь сейчас. После этого это более-менее умная грубая сила. Умная часть приходит от запоминания, поэтому вы не повторяете работу.
Вот базовый рекурсивный подход для Python, который делает следующее:
Организовать стол сыра в виде замороженного набора кортежей. Это можно хешировать для запоминания, и вы можете определить местоположение в наборе в постоянное время.
Создает условие ребра для конца (когда обе координаты равны N) и условие ребра, когда вы уходите с карты - это просто возвращает 0.
Использует lru_cache для запоминания. Вы можете легко реализовать это самостоятельно.
from functools import lru_cache
def hasCheese(table, location):
''' Helper function just to improve readability '''
return 1 if location in table else 0
@lru_cache()
def maxC(table, N, location = (0, 0)):
# edge conditions final square and off the grid:
if location[0] == N and location[1] == N:
return hasCheese(table, location)
if any(l > N for l in location):
return 0
# recursion
score_here = hasCheese(table, location)
return max(score_here + maxC(table, N, (location[0] + 1, location[1])),
score_here + maxC(table, N, (location[0], location[1] + 1))
)
t = frozenset([(2, 3), (3, 2), (4, 3), (4, 5), (5, 2)])
N = 5
print(maxC(t, N))
# prints 3
Если вы хотите сделать это сверху вниз, используя матрицу, вам нужно быть очень осторожным, чтобы у вас всегда был предыдущий набор индексов. Делать ошибки таким способом легче, потому что вам нужно правильно настроить индексы и порядок. Когда вы устанавливаете его как два вложенных увеличивающихся цикла, это означает, что следующим значением всегда будет текущая ячейка плюс максимум двух ячеек на единицу меньше - вы всегда должны смотреть назад в матрицу. Непонятно, что вы пытаетесь сделать, когда с нетерпением ждете этого:
dp[i][j] = table[i][j + 1]
, поскольку j+1 еще не определено.
Так как координаты сыра индексируются 1, простой путь вперед - сделать вашу матрицу индексированной с нулем и размером N + 1. Затем, когда вы запускаете свои циклы for в 1, вы всегда можете посмотреть и на более низкий индекс, не используя матрицу ниже, и избегать большой логики if/else. Например:
def hasCheese(table, location):
''' Helper function just to improve readability '''
return 1 if location in table else 0
def maxAverageOfPath(table, N):
# matrix is sized one unit bigger
dp = [[0 for i in range(N+1)] for j in range(N+1)]
# iterate 1-5 inclusive
for i in range(1, N+1):
for j in range(1, N+1):
# because the zeroth row and column are already zero, this works without undershooting the table
dp[i][j] = hasCheese(table, (i, j)) + max(dp[i][j-1], dp[i-1][j])
# solution is in the corner
return dp[N][N]
t = {(2, 3), (3, 2), (4, 3), (4, 5), (5, 2)}
N = 5
print(maxAverageOfPath(t, N)) #3
Когда вы закончите, ваша матрица будет выглядеть так:
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 1]
[0, 0, 1, 1, 1, 1]
[0, 0, 1, 2, 2, 3]
[0, 0, 2, 2, 2, 3]
Ваша начальная точка в (1, 1) начинается в верхнем правом углу, а ваш ответ - в левом нижнем углу.