поиск пути

[NiCola999]

Может кто видел решение этой задачи или подскажите как решать). Есть квадратная доска с числами. В левом верхнем углу стоит черепашка. Она умеет ходить только влево и вниз. Ей надо прийти в правый нижний угол, при этом она хочет, чтобы сумма чисел на пути была максимальной.Задача на динамическое программирование.

[Serge_Bliznykov]

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

p.s. С++ не знаю. но алгоритм могу расписать, например, на Паскале...

[m0nax]

она хочет, чтобы сумма чисел на пути была максимальной.

нужно пройти по всем наибольшим числам? собрать наибольшую сумму?
или просто при выборе куда шагать выбирать большее число из 2 доступных?
тобиш если поле будет
1 2 9 2
4 3 8 1
1 1 1 1
она пойдет 1 2 9 8 1 1 (22)
или все таки 1 4 3 8 1 1 (17)

[NiCola999]

но алгоритм могу расписать, например, на Паскале...

было бы неплохо

нужно пройти по всем наибольшим числам? собрать наибольшую сумму?

собрать наибольшую сумму

[NiCola999]

но алгоритм могу расписать, например, на Паскале...

было бы неплохо

нужно пройти по всем наибольшим числам? собрать наибольшую сумму?

собрать наибольшую сумму

[LeBron]

Опять рекурсивные идеи В таких задачах рекурсия неприемлима. Правильно сказано, динамическое программирование. Такие задачи в школе показывают, что бы стал понятен принцип ДП на таблицах. Заполняем матрицу максимумов (снизу вверх), и за n*n находим ответ.
Тут писать строк 5
Но мне как всегда лень.
Вот похожая задача:
В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).

Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.

Входные данные

Во входном файле INPUT.TXT задано два числа N и M - размеры таблицы (1<=N<=20, 1<=M<=20). Затем идет N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100).

Выходные данные

В выходной файл OUTPUT.TXT выведите минимальную сумму, потратив которую можно попасть в правый нижний угол.


И мое АС решение на Паскале:

var input,output:text;ar,ara:array[0..21,0..21] of longint;a,b,q,i,j:longint;
begin
assign(input,'input.txt');reset(input);assign(output,'output.txt');rewrite(output);
readln(input,a,b);for q:=1 to b do ara[a+1,q]:=maxint;for q:=1 to A do ara[q,b+1]:=maxint;

for i:=1 to a do begin for j:=1 to b do begin read(input,ar[i,j]);end;readln(input);end;

for i:=a downto 1 do begin for j:=b downto 1 do begin if (i=a) and (j=b) then ara[i,j]:=ar[i,j] else
begin if ara[i+1,j]>ara[i,j+1] then ara[i,j]:=ar[i,j]+ara[i,j+1] else
 ara[i,j]:=ar[i,j]+ara[i+1,j];end;end;end; 
writeln(output,ara[1,1]);

close(input);close(output);
end.

При желании - переоформить, поменять размерности, минимум и максимум, переписть на С++ - и задача готова. Суть ДП -

ans[i][j]=max(ans[i+1][j],ans[i][j+1])+ar[i][j]

И еще, "только влево и вниз" - имелось ввиду "только вправо и вниз"?

[NiCola999]

заполнение вспомогательного массива максимумами уже готово, обьясните как черепашке дойти до правого нижнего угла используя этот массив, при том что она может двгаться только вниз и влево, начальное положение в левом верхнем углу

[LeBron]

Сообщение от NiCola999

заполнение вспомогательного массива максимумами уже готово, обьясните как черепашке дойти до правого нижнего угла используя этот массив, при том что она может двгаться только вниз и влево, начальное положение в левом верхнем углу

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

[NiCola999]

да, все-таки вниз и вправо она может. Да, надо вывести путь

[girkoff]

Тут писать строк 5

, так как ты написал на паскале можно и в одну строчку, главно тогда enter нигде не ставить, без обид