Динамическое программирование - теория.

4. Черепашка

Задание:

На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она может переползать только в клетку справа или снизу и хочет, чтобы сумма всех чисел, оказавшихся у нее на пути, была бы максимальной. Определить эту сумму.

Формат входных данных
Первая строка — N — размер доски.
Далее следует N строк, каждая из которых содержит N целых чисел, представляющие доску.

Формат выходных данных
Одно число — максимальная сумма.

Решение:

Эта задача является классикой динамического программирования. Ни одно печатное или электронное пособие по решению задач не обходится без разбора “Черепашки”. Рассмотреть все возможные маршруты и просчитать их невозможно. Но можно свести задачу к аналогичной. Пусть нам известен “максимальный” путь для всех клеток, кроме правой нижней (функция 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];