В соответствии с комментарием @ גלעד ברקן, хитрость в решении этой проблемы заключается в добавлении дополнительного измерения, представляющего количество левых, взятых для достижения ячейки, в рекуррентное отношение.
Примечание: чтобы облегчить эту проблему, я перевернул строки данной матрицы так, чтобы разрешенные направления движения были уменьшены и вправо , а начальная ячейка стала (0, 0), а конечная ячейка стала (W - 1, H - 1), где W и H - ширина и высота матрицы соответственно. Кроме того, матрица и соответствующая таблица максимального счастья dp считаются в главном порядке строк, то есть matrix[y][x] - это значение в ячейке (x, y).
Наш true базовый случай - это счастье посещения начальной ячейки, которое либо matrix[0][0], либо 0, в зависимости от того, должно ли значение начальной ячейки быть включено в общее счастье , Однако у нас также есть два псевдо базовых случая, которые проще вычислить по сравнению с реальной рекурсией.
Эти псевдо базовые случаи - это крайний левый столбец (помните, что строки были перевернуты, так что это столбец крайний правый в исходной матрице) и самый верхний ряд. Отношение повторения для ячейки (0, y) (1 <= y < H) в крайнем левом столбце:
h[y][0][0] = matrix[y][0] + max(h[i][0][0] for i in 0 to y-1)
, где h - это наша таблица максимального счастья, а h[y][x][r] - максимальное счастье, полученное при переходе от клетки (0, 0) к (x, y) (в соответствии с данными правилами), получив r последовательных прав (или левых, для исходной матрицы без перевернутой строки) непосредственно перед тем, как достигнет (x, y). Таким образом, если r равно 0, последняя пройденная ячейка была одна непосредственно над текущей ячейкой. Единственный возможный способ добраться до ячейки в крайнем левом столбце - это выйти из ячейки прямо над ней.
Важно отметить, что в нашей таблице максимального счастья максимальное счастье для любой ячейки (x, y) дается максимумом h[y][x][r] для всех значений r. Если h является трехмерным массивом / списком, его также можно представить как max(h[y][x]).
Аналогично, отношение повторения для ячейки (x, 0) (1 <= x < W) в самой верхней строке:
h[0][x][x] = h[0][x-1][x-1] + matrix[0][x] - x
Это связано с тем фактом, что единственный способ добраться до ячейки в верхнем ряду - продолжать движение прямо от начальной ячейки. Количество прав, полученных для достижения ячейки в верхнем ряду, равно ее X-координате на основе 0, следовательно, штраф -x.
Теперь, когда у нас есть базовые случаи, мы можем перейти к рекуррентному отношению для ячейки (x, y), где 1 <= x < W и 1 <= y < H.
При установлении этого рекуррентного отношения, первое, что нужно отметить, это то, что есть только две возможности: либо последняя ячейка была над или слева от данной ячейки. Мы рассмотрим обе эти возможности.
Если бы последняя ячейка была выше данной ячейки, она имела бы координаты (x, j), где 0 <= j < y. Для максимального счастья счастье в последней клетке также должно быть максимальным. Таким образом, максимальное счастье в (x, y), когда последняя ячейка находится над данной ячейкой, определяется как
h[y][x][0] = matrix[y][x] + max(max(h[j][x]) for j in 0 to y-1)
Обратите внимание, что количество сделанных прав (r) равно 0, а max(h[j][x]) - это максимальное счастье, полученное при достижении ячейки (x, j) с любым количеством прав.
Еслипоследняя ячейка была слева от данной ячейки (или, другими словами, последний ход был вправо), ее координаты были бы просто (x - 1, y).Это потому, что мы можем перемещать только одну ячейку вправо за раз.В отличие от предыдущего случая, последняя позиция ячейки является постоянной.Однако количество последовательных прав (r) , полученных для достижения этой ячейки, является переменным.Поэтому мы должны рассмотреть все возможные значения для r.Поскольку может быть сделано минимум 1 право и максимум x прав, 1 <= r <= x.Для каждого значения r максимальное счастье этой ячейки - это максимальное счастье ячейки слева (последняя ячейка) для прав r - 1 плюс значение в (x, y) минус штраф (который составляет всего r - 1).В псевдокоде
for r in 1 to x:
h[y][x][r] = h[y][x-1][r-1] + matrix[y][x] - r
Теперь у нас есть все, что нужно для запуска алгоритма в восходящем или нисходящем подходе.Наш окончательный ответ, максимальное счастье, необходимое для достижения нижней правой (слева-вниз, для исходной матрицы, не перевернутой строкой), определяется как max(h[H-1][W-1]).
Собрав все вместе, мы получимследующий (Python-esque) восходящий алгоритм с временной сложностью алгоритма O(W^2 * H^2):
h[0][0][0] = matrix[0][0]
for x in range(1, W):
h[0][x][x] = h[0][x-1][x-1] + matrix[0][x] - x
for y in range(1, H):
h[y][0][0] = matrix[y][0] + max(h[i][0][0] for i in range(y))
for y in range(1, H):
for x in range(1, W):
for r in range(1, x + 1):
h[y][x][r] = h[y][x-1][r-1] + matrix[y][x] - r
h[y][x][0] = matrix[y][x] + max(max(h[j][x]) for j in range(y))
return max(h[H-1][W-1])
При ближайшем рассмотрении оказывается, что операция O(W) вычисления max(h[j][x]) может быть удаленапредварительно рассчитав его, сделав окончательную сложность по времени O(W * H^2).Обратите внимание, что эта оптимизация действительна только для восходящего подхода.Это работает, потому что ячейка (x, j) (где j < y) уже должна быть посещена при подходе снизу вверх.В приведенном ниже коде max(h[y][x]) хранится в h[y][x][W].
Полная оптимизированная версия восходящего алгоритма в Python 3 (включая данную примерную матрицу в качестве входных данных и реверсирование строк входных данных).матрица):
matrix = [[5, -2, -1, 5, 3, -99, 4, 0],
[5, -2, -1, -3, 3, -99, 2, -3],
[-98, -98, -98, -98, -98, -98, -98, -98],
[-99, -99, -99, -99, -99, -99, -99, -99],
[5, 0, -3, 5, -1, 7, -2, 2],
[1, 2, 7, 0, 0, 1, -1, -1]]
H = len(matrix)
W = len(matrix[0])
for row in matrix:
row.reverse()
h = [[[0] * (W + 1) for i in range(W)] for j in range(H)]
h[0][0][0] = matrix[0][0]
h[0][0][W] = h[0][0][0]
for x in range(1, W):
h[0][x][x] = h[0][x-1][x-1] + matrix[0][x] - x
h[0][x][W] = h[0][x][x]
for y in range(1, H):
h[y][0][0] = matrix[y][0] + max(h[i][0][0] for i in range(y))
h[y][0][W] = h[y][0][0]
for y in range(1, H):
for x in range(1, W):
h[y][x][0] = matrix[y][x] + max(h[j][x][W] for j in range(y))
h[y][x][W] = h[y][x][0]
for r in range(1, x + 1):
h[y][x][r] = h[y][x-1][r-1] + matrix[y][x] - r
h[y][x][W] = max(h[y][x][W], h[y][x][r])
print(h[H-1][W-1][W])