Динамическое программирование - метод решения задач, при котором задача разбивается на подзадачи, ответы к которым записываются в таблицу и используются при решении задачи; для решения каждой из подзадач используется тот же метод. Оно применимо только в том случае, когда подзадачи независимы друг от друга. Мы разберем несколько примеров использования динамического программирования:

Пример 1

Пусть у нас есть таблица A размера MxN, в клетках которой записаны целые числа. Назовем путь по клеткам таблицы, в котором за клеткой (i,j) следует одна из клеток (i+1,j), (i+1,j-1), (i+1,j+1), правильным. Пусть размер правильного пути - сумма всех чисел, стоящих в клетках таблицы, принадлежащих этому пути. Назовем правильный путь, начинающийся в одной из клеток (1,i), 1<=i<=N, и кончающийся в одной из клеток (M,j), 1<=j<=N, полным. Требуется найти полный путь минимального размера.

Например, в таблице на рис.1 выделен искомый путь:

Для решения задачи заведем таблицу B размера MxN, в которой B[i,j] равно минимальному размеру правильного пути от одной из клеток (1,k), 1<=k<=n, до клетки (i,j). Ясно, что B[1,j]=A[1,j]. Теперь, пусть мы уже вычислили B[i,j] для всех i<a. Найдем B[a,b] (1<=b<=N). Ясно, что в искомом пути клетке (a,b) предшествовала одна из клеток (a-1,b), (a-1,b-1), (a-1,b+1). Если это клетка (a-1,b), то минимальная длина пути из (1,k) в (a,b) равна B[a-1,b]+A[a,b], если это клетка (a-1,b-1), то минимальная длина данного пути равна B[a-1,b-1]+A[a,b], если это клетка (a-1,b+1), то минимальная длина данного пути равна B[a-1,b+1]+A[a,b]; значит, длина минимального пути из (1,k) в (a,b) равна наименьшему из этих трех чисел, т. е. B[a,b]=min(B[a-1,b],B[a-1,b-1],B[a-1,b+1])+A[a,b]. После того, как мы заполним таблицу B, минимальной длиной полного пути будет наименьшее из чисел B[m,i], где 1<=i<=n.

Найдем теперь по таблице B полный путь минимальной длины. Описанный ниже процесс называется обратным ходом. Пусть минимальная длина полного пути равна B[m,a]. Значит, в искомом пути клетка (m,a) была последней. Рассмотрим значения B[m-1,a], B[m-1,a-1],B[m-1,a+1]. Наименьшее из них стало основой для вычисления B[m,a] в первой части алгоритма. Найдем его. Пусть это B[m-1,b], где b - одно из чисел a,a-1,a+1. Ясно, что в искомом пути клетка (m-1,b) предшествовала клетке (m,a). Повторяя описанную операцию для клекти (m-1,b) вместо (m,a) и т. д., мы найдем весь искомый путь.

Реализация алгоритма:

const
  MinN = 2;
  MaxN = 100;
  MaxM = MaxN;

var
  M,N : Integer;
  A : array [1 .. MaxM,1 .. MaxN] of Integer;
  B : array [1 .. MaxM,1 .. MaxN] of Longint;
  Sol : array [1 .. MaxM] of Integer;

function Min(X,Y : Longint) : Longint;
begin
  if X<Y then
    Min:=X
  else   		
    Min:=Y;
end;

procedure Din_Example_1;
var
  I,J : Integer;
begin
  for I:=1 to N do
    B[1,I] := A[1,I];
  for I:=2 to M do
  begin
    B[I,1] := Min(B[I-1,1],B[I-1,2])+A[I,1];
    for J:=2 to N-1 do
      B[I,J] := Min(B[I-1,J],Min(B[I-1,J-1],B[I-1,J+1]))+A[I,J];
    B[I,N] := Min(B[I-1,N],B[I-1,N-1])+A[I,N];
  end;
  Sol[M]:=1;
  for I:=1 to N do
    if B[M,I]1) and (B[I-1,Sol[I]-1]<B[I-1,Sol[I-1]]) then
      Sol[I-1] := Sol[I]-1;
    if (Sol[I]<>N) and (B[I-1,Sol[I]+1]<B[I-1,Sol[I-1]]) then
      Sol[I-1] := Sol[I]+1;
  end;
  for I:=1 to M do
    Writeln(A[I,Sol[I]]);
end;

Например, для таблицы с рис. 1 этот алгоритм выдаст путь 1,6,5,1,5, являющийся искомым, а таблица B будет выглядеть так:

Пример 2

Рассмотрим все последовательности десятичных цифр четной длины (будем называть их номерами). Назовем номер счастливым, если сумма цифр в первой половине этого номера совпадает с суммой цифр во второй половине. Требуется определить количество счастливых номеров длины 2N.

Зафиксируем число K - сумму цифр в первой половине нашего номера. Ясно, что 0<=K<=9N. Пусть у нас есть таблица A такая, что A[i,j] - количество номеров длины i, сумма цифр которых равна j. Ясно, что для любого фиксированного K количество счастливых номеров равно A[N,K]^2 (действительно, мы можем выбрать левую и правую часть нашего номера независимо каждую из A[N,K] вариантов). Значит, искомое число равно сумме чисел A[N,K]^2 при K от 0 до 9N, и для решения задачи достаточно построить таблицу A.

Ясно, что при j>9*i или при j<0 мы имеем A[i,j]=0. Заметим, что A[1,i] равно 1 при 0<=i<=9 (есть только один номер длины 1, начинающийся на данную цифру - сама цифра). Теперь, пусть мы вычислили значения A[i,j] для всех i, меньших некоторого числа a, и нам требуется вычислить A[a,b]. Пусть T[a,b,c] - количество номеров длины a с суммой цифр b, последняя цифра которых равна c. Ясно, что T[a,b,c]=A[a-1,b-c], так как при отбрасывании последней цифры длина номера уменьшится на единицу, а сумма его цифр - на c. Теперь, A[a,b]=T[a,b,0]+T[a,b,1]+...+T[a,b,9], или A[a,b]=A[a-1,b]+A[a-1,b-1]+...+A[a-1,b-9]. Таким образом мы вычислим таблицу A.

Реализация алгоритма:

const
  MaxN = 5;

var
  A : array [1 .. MaxN,0 .. 9*MaxN] of Longint;

function Din_Example_2(N : Integer) : Longint;
var
  I,J,K : Integer;
  Res : Longint;
begin
  fillchar(A,sizeof(A),0);
  for I:=0 to 9 do
    A[1,I]:=1;
  for I:=2 to N do
    for J:=0 to 9*I do
      for K:=0 to 9 do
        if J>=K then
          A[I,J] := A[I,J] + A[I-1,J-K];
  Res := 0;
  for K:=0 to N*9 do
    Res := Res+A[N,K]*A[N,K];
  Din_Example_2 := Res;
end;

Например, при N=3 данный алгоритм выдаст ответ 55252.

Легко понять, что алгоритм требует O(N^2) времени и O(N^2) памяти.

Пример 3

Пусть у вас есть N предметов, i-й из которых (1<=i<=N) имеет вес W[i] и стоимость C[i]. Кроме того, у вас есть рюкзак, куда вы можете положить некоторые из этих предметов, причем их суммарный вес не должен превышать некоторого числа V. Все числа W[i] и число V - натуральные, и V не меньше каждого из W[i]. Требуется положить в рюкзак вещи как можно большей суммарной стоимости.

При небольшом V (V<=1000000) задачу можно решить с помощью динамического программирования. Пусть A - массив размера NxV, и A[i,j] - максимальная суммарная стоимость набора вещей с номерами, не превышающими i, суммарной массы j; если же такого набора не существует, то A[i,j]=-1. Ясно, что A[i,0]=0 (искомый набор-пустое множество). Пусть 1<a<=N, 1<=b<=V. Ясно, что A[a,b]=max(A[a-1,b],A[a-1,b-W[a]]+C[a]), так как A[a-1,b] - искомая величина для набора, не включающего a, а A[a-1,b-W[a]]+C[a] - для набора, включающего a. Ясно также, что ответом будет максимальное из чисел A[N,i], 0<=i<=V.

Реализация алгоритма (она несколько отличается от вышеописанного - массив A одномерный, а не двумерный):

const
  MaxN = 100;
  MaxV = 10000;

var
  N : Integer;
  V : Integer;
  W : array [1 .. MaxN] of Integer;
  C : array [1 .. MaxN] of Longint;
  A : array [0 .. MaxV] of Longint;

function Din_Example_3 : Longint;
var
  I,J : Integer;
begin
  Fillchar(A,sizeof(A),255);
  A[0] := 0;
  for I:=1 to N do
    for J:=V-W[I] downto 0 do
      if (A[J]<>-1) and (A[J+W[I]]<A[J]+C[I]) then
        A[J+W[I]] := A[J]+C[I];
  J := 0;
  for I:=0 to V do
    if A[J]<A[I] then
      J := I;
  Din_Example_3 := A[J];
end;

Например, если N=5, V=9, W=(1,5,6,8,10), C=(10,20,30,50,100), то агоритм выдаст число 60 (суммарная стоимость набора из вещей 1 и 4).

Алгоритм требует O(NV) времени и O(V) дополнительной памяти.