Recepty z programátorské kuchařky
Rekurzivní funkce a dynamické programování

Zobraz historii verzí Skryj historii verzí

Aktuální verze kuchařky: květen 2016

Leták 28-5květen 2016
+ Přidání Python 3 verze zdrojových kódů
* Drobné přeformulace a vylepšení čitelnosti
Leták 24-2listopad 2011(Martin Mareš, Petr Škoda)
* Přeformulována časová složitost u počítání Fibonacciho čísel
+ Přidán popis efektivnějšího počítání Fibonacciho čísel
+ Přidány cvičení a poznámky k problému batohu
* Odhad časové složitosti pro hledání nejdelší společné podposloupnosti přesunut nad kód algoritmu
Kuchařková knížka, 1. vydáníčervenec 2011(Martin Mareš, Petr Škoda)
* Poznámky a cvičení u Floyd-Washallova algoritmu rozděleny na dvě sekce
* Lepší rozdělení na odstavce
Leták 21-5červen 2009(Martin Mareš, Petr Škoda)
* Jazykové korektury
* Drobné přeformulace
+ Přidáno hledání nejdelší společné podposloupnosti
Leták 19-5duben 2007(Martin Mareš, Petr Škoda)
* První verze částečně spojena s jejím pokračováním
+ Přidána Fibonacciho čísla
* Drobné přeformulace textu
* Poznámka o hledání cesty ve Floyd-Washallově algoritmu přesunuta pod program
Leták 17-5květen 2005(Martin Mareš, Petr Škoda)
* Pokračování první verze
Leták 17-1září 2004(Martin Mareš, Petr Škoda)
* První verze

Rekurzivní funkce je taková funkce, která při svém běhu volá sama sebe, často i více než jednou. To typicky vede na exponenciální časovou složitost algoritmu.

Dynamické programování je technika, kterou lze z pomalého rekurzivního algoritmu vyrobit pěkný polynomiální, tedy až na výjimečné případy. Ale nepředbíhejme, nejdříve se podíváme na jednoduchý příklad rekurze.

Fibonacciho čísla

Budeme počítat n-té číslo Fibonacciho posloupnosti. To je posloupnost, jejímiž prvními dvěma členy jsou jedničky (F1 = 1, F2 = 1) a každý další člen je součtem dvou předchozích (Fn = Fn-1 + Fn-2 pro n>2). Začíná takto:

1123581321345589

Pro nalezení n-tého členu (ten budeme značit Fn) si napíšeme rekurzivní funkci Fibonacci(n), která bude postupovat přesně podle definice – zeptá se sama sebe rekurzivně, jaká jsou dvě předchozí čísla, a pak je sečte. Možná více řekne program:

def fibonacci(n):
  if n <= 2:
    return 1
  else:
    return fibonacci(n-1) + fibonacci(n-2)
function Fibonacci(n: integer): integer;
begin
  if n <= 2 then
    Fibonacci := 1
  else
    Fibonacci := Fibonacci(n-1) + Fibonacci(n-2)
end;

To, jak funkce volá sama sebe, si můžeme snadno nakreslit třeba pro výpočet čísla F5:

Strom volání pro F(5)

Vidíme, že se program rozvětvuje, což tvoří strom volání. V každém vrcholu tohoto stromu trávíme konstantní čas, takže časová složitost celého algoritmu je až na konstantu rovna počtu vrcholů tohoto stromu. Kolik to je, spočítáme jednoduchou úvahou.

Každý vrchol stromu vrací hodnotu, která je součtem hodnot v jeho synech. Proto je hodnota v kořeni rovna součtu hodnot v listech. V listech jsou ovšem jedničky (F1F2), takže listů musí být právě Fn a všech vrcholů dohromady aspoň Fn.

Proto na spočítání n-tého Fibonacciho čísla spotřebujeme čas alespoň takový, kolik je ono číslo samo. Ale jak velké takové Fn vlastně je? Můžeme třeba využít toho, že

Fn = Fn - 1 + Fn - 2 ≥ 2 · Fn - 2,

z čehož indukcí dokážeme

Fn ≥ 2n/2    pro n≥ 6.

Funkce Fibonacci má tedy alespoň exponenciální časovou složitost, což není nic vítaného.

Jak najít efektivnější algoritmus? Všimneme si, že některé podstromy jsou shodné. Zřejmě to budou ty části, které reprezentují výpočet stejného Fibonacciho čísla – v našem příkladě třeba třetího. Tyto výpočty opakujeme stále dokola.

Nenabízí se proto nic snazšího, než si jejich výsledky uložit a pak je kdykoliv vytáhnout jako pověstného králíka z klobouku s minimem námahy.

Právě zde je zmínka o králících příhodná. Legenda o Fibonacciho číslech vypráví, že k jejich objevu došlo při výzkumu rozmnožování králíků.

Leonardo Pisánský (známý též jako Fibonacci) totiž pěstoval králíky. První dva měsíce měl 1 pár, další měsíc měl 2 páry, pak 3, pak 5, …

Bude nám k tomu stačit jednoduché pole Pn prvcích, na počátku inicializované nulami. Kdykoliv budeme chtít spočítat některý člen, nejdříve se podíváme do pole, zda jsme ho již jednou nespočetli. A naopak jakmile hodnotu spočítáme, hned si ji do pole poznamenáme:

P = [0] * (N+1)
def fibonacci(n):
  if P[n] == 0:
    if n <= 2:
      P[n] = 1
    else:
      P[n] = fibonacci(n-1) + fibonacci(n-2)
  return P[n]
var P: array[1..MaxN] of integer;
function Fibonacci(n: integer): integer;
begin
  if P[n] = 0 then
  begin
    if n <= 2 then
      P[n] := 1
    else
      P[n] := Fibonacci(n-1) + Fibonacci(n-2)
  end;
  Fibonacci := P[n]
end;

Podívejme se, jak vypadá strom volání nyní:

Redukovaný strom volání pro F(5)

Na každý člen posloupnosti se tentokrát ptáme maximálně dvakrát – k výpočtu ho potřebují dva následující členy. To ale znamená, že funkci Fibonacci zavoláme maximálně 2n-krát, čili jsme touto jednoduchou úpravou zlepšili exponenciální složitost na lineární.

Zdálo by se, že abychom získali čas, museli jsme obětovat paměť, ale to není tak úplně pravda. V prvním příkladu sice nepoužíváme žádné pole, ale při volání funkce si musíme zapamatovat některé údaje, jako je třeba návratová adresa, parametry funkce a její lokální proměnné, a na to samotné potřebujeme určitě paměť lineární s hloubkou vnoření, v našem případě tedy lineární s n.

Určitě vás už také napadlo, že n-té Fibonacciho číslo se dá snadno spočítat i bez rekurze. Stačí prvky našeho pole P plnit od začátku – kdykoli známe P[1…k] = F1…k (všechny prvky pole na pozicích od 1 do k), dokážeme snadno spočítat i P[k+1]=Fk+1:

P = [0] * (N+1)
def fibonacci(n):
  P[1] = 1
  P[2] = 1
  for i in range(3, n):
    P[i] = P[i-1] + P[i-2]
  return P[n]
function Fibonacci(n: integer): integer;
var
  P: array[1..MaxN] of integer;
  i: integer;
begin
  P[1] := 1;
  P[2] := 1;
  for i := 3 to n do
    P[i] := P[i-1] + P[i-2];
  Fibonacci := P[n]
end;

Zopakujme si, co jsme postupně udělali – nejprve jsme vymysleli pomalou rekurzivní funkci, kterou jsme zrychlili zapamatováváním si mezivýsledků.

Nakonec jsme ale celou rekurzi „obrátili naruby“ a mezivýsledky počítali od nejmenšího k největšímu, aniž bychom se starali o to, jak se na ně původní rekurze ptala.

V případě Fibonacciho čísel je samozřejmě snadné přijít rovnou na nerekurzivní řešení, a dokonce si všimnout, že si stačí pamatovat jen poslední dvě hodnoty, a paměťovou složitost tak zredukovat na konstantní.

Zmíněný obecný postup zrychlování rekurze nebo rovnou řešení úlohy od nejmenších podproblémů k těm největším funguje i pro řadu složitějších úloh. Obvykle se mu říká dynamické programování.

Problém batohu

Je dáno N předmětů o hmotnostech m1,… ,mN (celočíselných) a také číslo M (nosnost batohu). Úkolem je vybrat některé z předmětů tak, aby součet jejich hmotností byl co největší, ale přitom nepřekročil M. Předvedeme si algoritmus, který tento problém řeší v čase O(MN).

Náš algoritmus bude používat pomocné pole A[0… M] a jeho činnost bude rozdělena do N kroků. Na konci k-tého kroku bude prvek A[i] nenulový právě tehdy, jestliže z prvních k předmětů lze vybrat předměty, jejichž součet hmotností je přesně i.

Před prvním krokem (po nultém kroku) jsou všechny hodnoty A[i] pro i>0 nulové a A[0] má nějakou nenulovou hodnotu, řekněme -1.

Všimněme si, jak kroky algoritmu odpovídají podúlohám, které řešíme – v prvním kroku vyřešíme podúlohu tvořenou jen prvním předmětem, ve druhém kroku prvními dvěma předměty, pak prvními třemi předměty atd.

Popišme si nyní k-tý krok algoritmu. Pole A budeme procházet od konce, tj. od i=M. Pokud je hodnota A[i] stále nulová, ale hodnota A[i-mk] je nenulová, změníme hodnotu uloženou v A[i] na k (později si vysvětlíme, proč zrovna na k).

Nyní si rozmyslíme, že po provedení k-tého kroku odpovídají nenulové hodnoty v poli A hmotnostem podmnožin z prvních k předmětů (podmnožina je v podstatě jen výběr nějaké části předmětů).

Pokud je hodnota A[i] nenulová, pak buď byla nenulová před k-tým krokem (a v tom případě odpovídá hmotnosti nějaké podmnožiny prvních k-1 předmětů), anebo se stala nenulovou v k-tém kroku.

Potom ale hodnota A[i-mk] byla před k-tým krokem nenulová, a tedy existuje podmnožina prvních k-1 předmětů, jejíž hmotnost je i-mk. Přidáním k-tého předmětu k této podmnožině vytvoříme podmnožinu předmětů hmotnosti přesně i.

Naopak, pokud lze vytvořit podmnožinu X hmotnosti i z prvních k předmětů, pak takovou podmnožinu X lze buď vytvořit jen z prvních k-1 předmětů, a tedy hodnota A[i] je nenulová již před k-tým krokem, anebo k-tý předmět je obsažen v takové množině X.

Potom ale hodnota A[i-mk] je nenulová před k-tým krokem (hmotnost podmnožiny X bez k-tého prvku je i-mk) a hodnota A[i] se stane nenulovou v k-tém kroku.

Po provedení všech N kroků odpovídají nenulové hodnoty A[i] přesně hmotnostem podmnožin ze všech předmětů, které máme k dispozici. Speciálně největší index i0 takový, že hodnota A[i0] je nenulová, odpovídá hmotnosti nejtěžší podmnožiny předmětů, která nepřekročí hmotnost M.

Nalézt jednu množinu této hmotnosti také není obtížné: V k-tém kroku jsme měnili nulové hodnoty v poli A na hodnotu k, takže v A[i0] je uloženo číslo jednoho z předmětů nějaké takové množiny, v A[i0-mA[i0]] číslo dalšího předmětu atd. Zdrojový kód tohoto algoritmu lze nalézt níže.

Časová složitost algoritmu je O(NM), neboť se skládá z N kroků, z nichž každý vyžaduje čas O(M). Paměťová složitost činí O(N+M), což představuje paměť potřebnou pro uložení pomocného pole A a hmotností daných předmětů.

Cvičení a poznámky

  • Proč pole A procházíme pozadu a ne popředu?
  • Složitost algoritmu vypadá jako polynomiální, ale to je trochu podvod. Závisí totiž na hodnotě M. Pokud tuto hodnotu na vstupu zapíšeme obvyklým způsobem, tedy v desítkové nebo dvojkové soustavě, použijeme řádově log M cifer.

    Naše M proto bude vzhledem k délce vstupu až exponenciálně velké. To je typický příklad takzvaného pseudopolynomiálního algoritmu – tedy takového, jenž je vzhledem k hodnotám na vstupu polynomiální, ale k délce vstupu exponenciální. Podrobnosti si můžete přečíst v kuchařce o těžkých úloháchv kapitole o těžkých úlohách na straně .

# Již existující proměnné:
# N - počet předmětů
# M - hmotnostní omezení
# hmotnosti - pole hmotností jednotlivých předmětů

A = [0] * M

A[0] = 1
for k in range(N):
  for i in range(M, hmotnost[k]-1, -1):
    if (A[i-hmotnost[k]] != 0) and (A[i] == 0):
      A[i] = k
  i = M
  while A[i] == 0:
    i -= 1
  print("Maximální hmotnost: {}" .format(i))
  print("Předměty v množině:", end="")
  while A[i] != -1:
    print(" {}" .format(A[i]), end="")
    i = i - hmotnost[A[i]]
var N: integer; {   počet předmětů   }
    M: integer; { hmotnostní omezení }
    hmotnost: array[1..N] of integer;
                { hmotnosti daných předmětů }
    A: array[0..M] of integer;
    i, k: integer;
begin
  A[0]:=-1;
  for i:=1 to M do A[i]:=0;
  for k:=1 to N do
    for i:=M downto hmotnost[k] do
      if (A[i-hmotnost[k]]<>0) and (A[i]=0) then
        A[i]:=k;
  i:=M; while A[i]=0 do i:=i-1;
  writeln('Maximální hmotnost: ',i);
  write('Předměty v množině:');
  while A[i]<>-1 do begin
    write(' ',A[i]);
    i:=i-hmotnost[A[i]];
  end;
  writeln;
end.

Nejkratší cesty a Floydův-Warshallův algoritmus

Náš další příklad bude z oblasti grafových algoritmů, ale zkusíme si jej nejdříve říci bez grafů:

Bylo-nebylo-je N měst. Mezi některými dvojicemi měst vedou (obousměrné) silnice, jejichž (nezáporné) délky jsou dány na vstupu. Předpokládáme, že silnice se jinde než ve městech nepotkávají (pokud se kříží, tak mimoúrovňově).

Úkolem je spočítat nejkratší vzdálenosti mezi všemi dvojicemi měst, tj. délky nejkratších cest mezi všemi dvojicemi měst.

Cestou rozumíme posloupnost měst takovou, že každá dvě po sobě následující města jsou spojené silnicí, a délka cesty je součet délek silnic, které tato města spojují.

V grafové terminologii tedy máme daný ohodnocený neorientovaný graf a chceme zjistit délky nejkratších cest mezi všemi dvojicemi jeho vrcholů.

Půjdeme na to následovně – vzdálenosti mezi městy jsou na začátku algoritmu uloženy ve dvourozměrném poli D, tj. D[i][j] je vzdálenost z města i do města j. Pokud mezi městy i a j nevede žádná silnice, bude D[i][j]=∞ (v programu bude tato hodnota rovna nějakému dostatečně velkému číslu).

V průběhu výpočtu si budeme na pozici D[i][j] udržovat délku nejkratší dosud nalezené cesty mezi městy i a j.

Algoritmus se skládá z N fází. Na konci k-té fáze bude v D[i][j] uložena délka nejkratší cesty mezi městy ij, která může procházet skrz libovolná z měst 1,… ,k.

V průběhu k-té fáze tedy stačí vyzkoušet, zda je mezi městy i a j kratší stávající cesta přes města 1,… ,k-1, jejíž délka je uložena v D[i][j], nebo nová cesta přes město k.

Pokud nejkratší cesta prochází přes město k, můžeme si ji rozdělit na nejkratší cestu z i do k a nejkratší cestu z k do j. Délka takové cesty je tedy rovna D[i][k]+D[k][j].

Takže pokud je součet D[i][k]+D[k][j] menší než stávající hodnota D[i][j], nahradíme hodnotu na pozici D[i][j] tímto součtem, jinak ji ponecháme.

Z popisu algoritmu přímo plyne, že po N-té fázi je na pozici D[i][j] uložena délka nejkratší cesty z města i do města j.

Protože v každé z N fází algoritmu musíme vyzkoušet všechny dvojice i a j, vyžaduje každá fáze čas O(N2). Celková časová složitost našeho algoritmu tedy je O(N3). Co se paměti týče, vystačíme si s polem D a to má velikost O(N2).

Program bude vypadat následovně:

for k in range(N):
  for i in range(N):
    for j in range(N):
      if d[i][k] + d[k][j] < d[i][j]:
        d[i][j] = d[i][k] + d[k][j]
var N: integer; { počet měst }
    D: array[1..N] of array[1..N] of longint;
      { délky silnic mezi městy, D[i][i]=0,
        místo neexistujících je "nekonečno" }
    i, j, k: integer;
begin
  for k:=1 to N do
    for i:=1 to N do
      for j:=1 to N do
        if D[i][k]+D[k][j] < D[i][j] then
            D[i][j]:=D[i][k] + D[k][j];
end.
Ilustrace: Hroch turista.

Popišme si ještě, jak bychom postupovali, kdybychom kromě vzdáleností mezi městy chtěli nalézt i nejkratší cesty mezi nimi.

To lze jednoduše vyřešit například tak, že si navíc budeme udržovat pomocné pole E[i][j] a do něj při změně hodnoty D[i][j] uložíme nejvyšší číslo města na cestě z i do j délky D[i][j] (při změně v k-té fázi je to číslo k).

Máme-li pak vypsat nejkratší cestu z i do j, vypíšeme nejprve cestu z i do E[i][j] a pak cestu z E[i][j] do j. Tyto cesty nalezneme stejným (rekurzivním) postupem.

Poznámky

  • Popis algoritmu vysloveně svádí k „rejpnutí“: Jak víme, že spojením dvou cest, které provádíme, vznikne zase cesta (tj. že se na ní nemohou nějaké vrcholy opakovat)?

    To samozřejmě nevíme, ale všimněme si, že kdykoliv by to cesta nebyla, tak si ji nevybereme, protože původní cesta bez vrcholu k bude vždy kratší nebo alespoň stejně dlouhá… tedy dokud se v naší zemi nevyskytuje cyklus záporné délky. To bychom měli přidat do předpokladů našeho algoritmu, kdybychom byli pedanti.

  • Pozor na pořadí cyklů – program vysloveně svádí k tomu, abychom psali cyklus pro k jako vnitřní… jenže pak samozřejmě nebude fungovat.

Cvičení

  • Jak by algoritmus fungoval, kdyby silnice byly jednosměrné?
  • Na první pohled nejpřirozenější hodnota, kterou bychom mohli použít pro , je maxint. To ovšem nebude fungovat, protože ∞+∞ přeteče. Stačí maxint div 2?
  • Hodnoty v poli si přepisujeme pod rukama, takže by se nám mohly poplést hodnoty z předchozí fáze s těmi z fáze současné. Ale zachrání nás to, že čísla, o která jde, vyjdou v obou fázích stejně. Proč?

Nejdelší společná podposloupnost

Poslední příklad dynamického programování, který si předvedeme, se bude týkat posloupností. Mějme dvě posloupnosti čísel A a B.

Chceme najít jejich nejdelší společnou podposloupnost, tedy takovou posloupnost, kterou můžeme získat z AB odstraněním některých prvků. Například pro posloupnosti

A= 2 3 3 1 2 3 2 2 3 1 1 2
B= 3 2 2 1 3 1 2 2 3 3 1 2 2 3

je jednou z nejdelších společných podposloupností tato posloupnost:

C=2 3 1 2 2 3 1 2.

Jakým způsobem můžeme takovou podposloupnost najít? Nejdříve nás asi napadne vygenerovat všechny podposloupnosti a ty pak porovnat.

Jakmile si ale spočítáme, že všech podposloupností posloupnosti o délce n je 2n (každý prvek nezávisle na ostatních buď použijeme, nebo ne), najdeme raději nějaké rychlejší řešení.

Zkusme využít následující myšlenku: vyřešíme tento problém pouze pro první prvek posloupnosti A. Pak najdeme řešení pro první dva prvky A, přičemž využijeme předchozích výsledků. Takto pokračujeme pro první tři, čtyři, … až n prvků.

Nejprve si rozmyslíme, co všechno si musíme v každém kroku pamatovat, abychom z toho dokázali spočíst krok následující. Určitě nám nebude stačit pamatovat si pouze nejdelší podposloupnost, jenže množina všech společných podposloupností je už zase moc velká.

Podívejme se tedy detailněji, jak se změní tato množina při přidání dalšího prvku k A: Všechny podposloupnosti, které v množině byly, tam zůstanou a navíc přibude několik nových, končících právě přidaným prvkem.

Ovšem my si podposloupnosti pamatujeme proto, abychom je časem rozšířili na nejdelší společnou podposloupnost.

Takže pokud známe nějaké dvě stejně dlouhé podposloupnosti PQ končící nově přidaným prvkem v A a víme, že P končí v B dříve než Q, stačí si z nich pamatovat pouze P.

V libovolném rozšíření Q-čka totiž můžeme Q vyměnit za P a získat tím stejně dlouhou společnou podposloupnost.

Proto si stačí pro již zpracovaných a prvků posloupnosti A pamatovat pro každou délku l tu ze společných podposloupností A[1… a] a B délky l, která v B končí na nejlevějším možném místě.

Dokonce nám bude stačit si místo celé podposloupnosti uložit jen pozici jejího konce v B. K tomu použijeme dvojrozměrné pole D[a,l].

Ještě si dovolíme jedno malé pozorování: Koncové pozice uložené v poli D se zvětšují s rostoucí délkou podposloupnosti, čili D[a,l]<D[a,l+1], protože posloupnosti délky l+1 nejsou ničím jiným než rozšířeními posloupností délky l o 1 prvek.

Teď již výpočet samotný:

Pokud už známe celý a-tý řádek pole D, můžeme z něj získat (a+1)-ní řádek. Projdeme postupně posloupnost B. Když najdeme v B prvek A[a+1] (ten právě přidávaný do A), můžeme rozšířit všechny podposloupnosti končící před aktuální pozicí v B.

Nás bude zajímat pouze ta nejdelší z nich, protože rozšířením všech kratších získáme posloupnost, jejíž koncová pozice je větší než koncová pozice některé posloupnosti, kterou již známe. Rozšíříme tedy tu nejdelší podposloupnost a uložíme ji místo původní podposloupnosti.

Toto provedeme pro každý výskyt nového prvku v posloupnosti B. Všimněme si, že nemusíme procházet pole s podposloupnostmi stále od začátku, ale můžeme se v něm posouvat od nejmenší délky k největší.

Ukážeme si, jak vypadá zaplněné pole hodnotami při řešení problému s posloupnostmi z našeho příkladu. Řádky jsou pozice v A, sloupce délky podposloupností.

D 1 2 3 4 5 6 7 8 9101112
1 2 - - - - - - - - - - -
2 1 5 - - - - - - - - - -
3 1 5 9 - - - - - - - - -
4 1 4 611 - - - - - - - -
5 1 2 5 712 - - - - - - -
6 1 2 3 7 914 - - - - - -
7 1 2 3 7 812 - - - - - -
8 1 2 3 7 81213 - - - - -
9 1 2 3 5 8 91314 - - - -
10 1 2 3 4 6 91114 - - - -
11 1 2 3 4 6 91114 - - - -
12 1 2 3 4 6 71112 - - - -

Zbývá popsat, jak z těchto dat zvládneme rekonstruovat hledanou nejdelší společnou podposloupnost (NSP).

Ukážeme si to na našem příkladu – jelikož poslední nenulové číslo na posledním řádku je v 8. sloupci, má hledaná NSP délku 8.

D[12, 8]=12 říká, že poslední písmeno NSP je na pozici 12 v posloupnosti B. Jeho pozici v posloupnosti A určuje nejvyšší řádek, ve kterém se tato hodnota také vyskytuje, v našem případě je to řádek 12. Druhé písmeno tedy budeme určovat z D[10, 7], třetí z D[9, 6], atd.

Jednou z hledaných podposloupností je tedy:

poslupnost: 2 3 1 2 2 3 1 2
indexy v A:1 2 4 5 7 91012
indexy v B:2 5 6 7 8 91112

Již zbývá jen odhadnout složitost algoritmu. Časově nejnáročnější byl vlastní výpočet hodnot v poli, který se skládá ze dvou hlavních cyklů o délce |A| a |B|, což jsou délky posloupností A a B.

Vnořený cyklus while proběhne celkem maximálně |A|-krát a časovou složitost nám nezhorší. Můžeme tedy říct, že časová složitost je O(|A| · |B|).

Posloupnosti jsme si prohodili tak, aby první byla ta kratší, protože pak jsou maximální délka společné podposloupnosti i počet kroků algoritmu rovny délce kratší posloupnosti, a tedy i velikost pole s daty je kvadrát této délky.

Paměťovou složitost odhadneme O(N2+M), kde N je délka kratší posloupnosti a M té delší.

...
if LA > LB:
  (C, A, B) = (A, B, C)
  (T, LA, LB) = (LA, LB, T)

for i in range(LA):
  d[0][i] = LB

L = 0
MaxL = 0
for i in range(LA):
  for j in range(LA):
    d[i][j] = d[i-1][j]

  L = 0
  for j in range(LB):
    if B[j] == A[i-1]:
      while (L == 0) or (d[i-1][L] < j):
        L += 1
      if d[i][L] >= j:
        d[i][L] = j
    if L > MaxL:
      MaxL = L

  LC = MaxL
  j = LA
  for i in range(LC, 0, -1):
    while d[j-1][i] == d[j][i]:
      j -= 1
    C[i-1] = A[j-1]
    j -= 1

...
program Podposloupnost;
var
  A, B, C: array[0..MaxN - 1] of Integer;
  LA, LB, LC: Integer;  { Délky posloupností }
  D: array[0..MaxN, 1..MaxN] of Integer;
  I, J, L, MaxL, T: Integer;
begin
  ...
  if LA > LB then begin { A bude kratší z obou }
    C := A;
    A := B;
    B := C;
    T := LA;
    LA := LB;
    LB := T;
  end;

  for I := 1 to LA do
    D[0, I] := LB;

  L := 0;
  MaxL := 0;
  for I := 1 to LA do begin
    for J := 1 to LA do
      D[I, J] := D[I-1, J];

    L := 0;
    for J := 0 to LB-1 do
      if B[J] = A[I-1] then begin
        while (L = 0) or (D[I-1, L] < J) do
          L:=L+1;
        if D[I, L] >= J then
          D[I, L] := J;
      end;
      if L > MaxL then MaxL := L;
  end;

  LC := MaxL;
  J := LA;
  for I := LC downto 1 do
  begin
    while D[J-1, I] = D[J, I] do J:=J-1;
    C[I-1] := A[J-1];
    J:=J-1;
  end;
  ...
end.
Dnešní menu servírovali
Martin Mareš a Petr Škoda