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

[MAKEDON]

При решение задач столкнулся с таким понятием, как динамическое программирование. Вот задача на поиск всех возможных путей и нахождение наиболее быстрого. Объясните на примере этой задачи, как вообще они решаются. Язык - значения не имеет.

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

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

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

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

Пример входного файла
3 4
1 1 1 1
5 2 2 100
9 4 2 1

Пример выходного файла
8

[Levsha100]

Эта задача решается с помощью ориентированных графов.
//Только почему такое странное название темы? О_О

[Sazary]

Вот, недавно было такое: http://programmersforum.ru/showthread.php?t=60512

[Somebody]

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

Эта задача решается с помощью ориентированных графов.
//Только почему такое странное название темы? О_О

Потому что динамическим программированием решается легче, чем графами. Вроде даже на школьной олимпиаде эта задача как-то была.

[MAKEDON]

Да, эта задача с какой-то олимпиады. А можете представить решение с комментириями? А то никак в этой теме не могу разобраться..

[Somebody]

a[0][1] = 0;
for (int x = 2; x <= m; x++)
a[0][x] = numeric_limits<int>::max();
for (int y = 1; y <= n; y++)
{
a[y][0] = numeric_limits<int>::max();
for (int x = 1; x <= m; x++)
cin >> a[y][x];
}
for (int y = 1; y <= n; y++)
for (int x = 1; x <= m; x++)
a[y][x] += min(a[y - 1][x], a[y][x - 1]);
[/code]
Минимальная сумма, полученная по пути для клетки, - это число в этой клетке плюс минимум из суммы для клетки слева и клетки сверху. Почитай Википедию про динамическое программирование, запусти пошагово на примере и посмотри.

[megachuhancer]

Эта задача решается с помощью ориентированных графов.
//Только почему такое странное название темы? О_О

Неее, это задача именно на динамическое программирование.
Идея такая. Пусть мы сейчас вычисляем оптимальную характеристику для [i, j] клетки. Пусть нам уже известна оптимальная характеристика для клеток левее этой клетки в этой же строке(i-той) и для всех клеток в предыдущих строках(с номером < i). Тогда как мы можем попасть в клетку [i, j]? Из клеток [i - 1, j] и [i, j - 1]. Надо только учитывать что в клетки первой строки мы можем попасть только слева и в клетки первого столбца только сверху. Выбираем минимум и не забываем добавить стоимость прохождения через саму клетку. Вот исходник, правда работает с числами только от 0 до 9 в каждой клетке. Таковы были ограничения задачи, которую я решал. Но главное, чтобы логика работы была понятна, а там переделаешь как тебе надо. Например на Delphi или C++. Там правда есть ещё несколько технических моментов, обусловленных ограничениями задачи, которую я решал, и Turbo Pascal'я на котором я её тогда писал.
Эта программа правда рисует в ASCII оптимальный маршрут, вместо того, чтобы выводить необходимое число, но из неё можно взять кусок основной логики. А, да, и ещё во входном файле цифры матрицы надо записывать без пробелов.

program routeproblem;
{$r+,q+}
const
	from_up=10;
	from_left=11;
	initial=12;
	route=13;
var
	c:char;
	T:array[1..250,1..250]of byte;
	M2:array[1..250]of integer;
	n,i,j:integer;
begin
	assign(input,'route.in');
	assign(output,'route.out');
	reset(input);
	rewrite(output);
	readln(n);
	i:=0;
	while not ((i=n) and (j=n)) do begin
		inc(i);
		j:=0;
		while not eoln do begin
			read(c);
			inc(j);
			T[i,j]:=ord(c)-ord('0');
		end;
		readln;
	end;
	M2[1]:=T[1,1];
	T[1,1]:=initial;
	for i:=2 to n do begin
		M2[i]:=T[1,i]+M2[i-1];
		T[1,i]:=from_left;
	end;
	for i:=2 to n do begin
		M2[1]:=T[i,1]+M2[1];
		T[i,1]:=from_up;
		for j:=2 to n do begin
			if M2[j]<M2[j-1] then begin
				M2[j]:=M2[j]+T[i,j];
				T[i,j]:=from_up;
			end
			else begin
				M2[j]:=M2[j-1]+T[i,j];
				T[i,j]:=from_left;
			end;
		end;
	end;
	i:=n;
	j:=n;
	while not (T[i,j]=initial) do begin
		if T[i,j]=from_left then begin
			T[i,j]:=route;
			dec(j);
		end;
		if T[i,j]=from_up then begin
			T[i,j]:=route;
			dec(i);
		end;
	end;
	T[1,1]:=route;
	for i:=1 to n do begin
		for j:=1 to n do
			if T[i,j]=route
			then write('#')
			else write('-');
		writeln;
	end;
	close(input);
	close(output);
end.

----------------------------------------------------------------------------------------------------------------------------------
Ладно, короче Самому стало интересно, так что не поленился написать то, что тебе нужно.

#include <cstdio>
#include <algorithm>
using namespace std;
int a[30][30], n, m;
int main() {
   scanf(" %d %d", &n, &m);
   for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
         scanf(" %d", &a[i][j]);
   for(int i = 1; i < m; i++) a[0][i] += a[0][i - 1];
   for(int i = 1; i < n; i++) a[i][0] += a[i - 1][0];
   for(int i = 1; i < n; i++)
      for(int j = 1; j < m; j++)
         a[i][j] += min(a[i - 1][j], a[i][j - 1]);
   printf("%d", a[n - 1][m - 1]);
   return 0;
}

-----------------------------------------------------------------------------------------------------------------------------------

Объясните на примере этой задачи, как вообще они решаются.

Нуу... Это трудно объяснить кратко. Я ведь и сам не каждую задачу на динамическое программирование решу. Короче, основная идея в табличном методе решения задач. Первоначально по английски это называлось memorization или как-то в этом роде. То есть надо забить в память промежуточные результаты решения подзадач. То есть надо чётко представлять какую характеристику мы хотим максимизировать(минимизировать) и как она зависит от остальных. Если делать по науке, то надо сначала выразить нужную характеристику рекуррентно. А потом, если есть локальный максимум(минимум), надо его собственно и найти(по формуле, если так можно выразиться), а не перебирать все варианты. И вообще, что я взялся рассказывать... Действительно, Википедия лучше обо всём расскажет
-----------------------------------------------------------------------------------------------------------------------------------
Из литературы могу рекомендовать:
1) Кормен, Ривест, Лейзерсон, Штайн. Алгоритмы: построение и анализ
2) Ф.Меньшиков. Олимпиадные задачи по программированию.
Правда, вторая немного устарела, в том плане, что на олимпиадах сейчас задачки и покруче бывают.