Эта задача является классикой динамического программирования. Ни одно печатное или электронное пособие по решению задач не обходится без разбора “Черепашки”. Рассмотреть все возможные маршруты и просчитать их невозможно. Но можно свести задачу к аналогичной. Пусть нам известен “максимальный” путь для всех клеток, кроме правой нижней (функция F(X, Y)). Все нужные маршруты проходят через одну из клеток, смежных с этим углом (их всего две). Максимальный же маршрут проходит через ту клетку из двух, для которой значение функции F больше. Остается только правильно выполнить отсечение:
Function F(x,y:integer):longint; begin if B[x, y] = –1 then if F(x-1, y) > F(x, y - 1) then B[x, y] := F(x - 1, y) + A[x, y] else B[x, y] := F(x, y - 1) + A[x, y]; F := B[x, y] end;
Теперь необходимо подумать о граничных условиях. Логически правильнее было бы просчитать нашу функцию для левой и верхней границы. Это делается легко, так как для этих клеток существует только один маршрут (непосредственно вдоль границы). Но еще проще ввести в рассмотрение фиктивные нулевые строку и столбец и присвоить им нулевые значения. Действительно, эти клетки, в принципе, недостижимы, поэтому максимальная сумма равна нулю.
Итеративное заполнение массива также довольно просто. После введения граничных условий (любых из рассмотренных выше) дальнейшее заполнение осуществляется двойным циклом:
for i:=1 to N do for j:=1 to N do if B[i - 1, j] > B[i, j - 1] then B[i, j] := B[i - 1, j] + A[i, j] else B[i, j] := B[i, j - 1] + A[i, j];