programowanie dynamiczne - wydawanie reszty

Witam
Mam do napisana program do wydawania reszty za pomocą programowania dynamicznego. Program mi wypisuje ile i jakich nominałów wyda w przypadku konkretnej kwoty.
Problem w tym że nie rozumiem o co chodzi w programowaniu dynamicznym :-/
Czy mógłby ktoś mi to wytłumaczyć prostym językiem?

Pozdrawiam

Postaram się wyjaśnić jak najprościej.
Na początku staramy się rozwiązać jakiś bardzo łatwy problem, czyli wydanie reszty równej zero - czyli nie wydanie nic. Potem liczymy w jaki sposób możemy wydać resztę jeden - oczywiście tylko jeżeli mamy pieniądze o nominale jeden.
Załóżmy, że doszliśmy do n i chcemy dowiedzieć się czy możemy je wydać. Jeżeli mamy pieniądze o nominałach powiedzmy a1,a2,...,ak to dla każdego nominału może być następująca sytuacja(rozważam ai):
Jeżeli n - ai da się wydać to do tamtej reszty dodajemy ai i mamy sposób na wydanie n. Jeżeli n - ai nie można wydać to wtedy nie możemy użyć nominału ai do wydania tej reszty.
A jeżeli chcesz wydać najmniejszą liczbą monet to wtedy pamiętasz iloma monetami możesz wydać każdą resztę. i jak rozważasz jakieś n to dla każdego nominału bierzesz minimum z liczby monet do wydania dla n - ai plus jeden(gdyż dodajemy dodatkową monetę o wartości ai)

Programowanie dynamiczne składa sie z kilku faz:

1. Czy w ogóle dany problem da sie tak rozwiazać? To jest pytanie o tzw "własność optymalnej podstruktury". Na czym to polega? Musisz zadać sobie pytanie "czy znając rozwiązanie problemu mniejszego, jesteś w łatwy sposób w stanie poznać rozwiązanie problemu większego". W przypadku reszty wyraźnie tak jest: jeśli wiem iloma monetami mogę wydać 100zł, to wiem od razu iloma moge wydać 101zł (zakładając że mam monety 1zł).
2. Jeśli pierwszy punkt jest spełniony to zaczynamy rozwiązywanie problemu począwszy od podproblemów najmniejszych. W przypadku reszty, zaczynamy obliczać iloma monetami możemy wydać 0,1,2... itd

Można na to patrzeć też z innej perspektywy: to jest rozwiązywanie rekurencji od końca. Zauważ ze aby policzyć na ile sposobów możemy wydać 101zł, moglibyśmy to zrobic pewną funkcją rekurencyjną:

int funkcja(kwota)
{
  if(kwota == 0)
    return 0;
  if(kwota < 0)
    return maxint;
  return minimum(funkcja(kwota-5),funkcja(kwota-2, funkcja(kwota-1))
}

gdzie funkcja() mówi nam na ile sposobów mozemy wydać daną kwotę.
Jaki jest problem z tą funkcja rekurencyjną? Gdybyśmy narysowali sobie drzewko rekurencji z jakiej ta funkcja korzysta to nagle okaże się że wielokrotnie rozwiazujemy ten sam problem! Tzn wielokrotnie obliczamy funkcja(x) dla tego samego argumentu x!

Podejście dynamiczne z tablicowaniem pozwala nam tego uniknąć. Tak samo wielokrotnie korzystamy z wartości funkcji dla tego samego argumentu, ale my ta wartość już mamy policzoną, a nie obliczamy ją za kazdym razem od nowa.

Ja miałem zrobione tak:

program reszta;

uses crt;

var
   m : integer;
   x : Currency;

begin
    m:=0;
    writeln('Podaj, kwote do wydania: ');
    readln(x);
    while x >= 5 do
    begin
     x:=x-5;
     m:=m+1;
    end;
    writeln(m,' monet 5 zlotowych');
    m:=0;

    while x >= 2 do
    begin
     x:=x-2;
     m:=m+1;
    end;
    writeln(m,' monet 2 zlotowych');
    m:=0;

    while x >= 1 do
    begin
     x:=x-1;
     m:=m+1;
    end;
    writeln(m,' monet 1 zlotowych');
    m:=0;

    while x >= 0.5 do
    begin
     x:=x-0.5;
     m:=m+1;
    end;
    writeln(m,' monet 0.5 zlotowych');
    m:=0;

    while x >= 0.2 do
    begin
     x:=x-0.2;
     m:=m+1;
    end;
    writeln(m,' monet 0.2 zlotowych');
    m:=0;

    while x >= 0.1 do
    begin
     x:=x-0.1;
     m:=m+1;
    end;
    writeln(m,' monet 0.1 zlotowych');
    m:=0;


    while x >= 0.05 do
    begin
     x:=x-0.05;
     m:=m+1;
    end;
    writeln(m,' monet 0.05 zlotowych');
    m:=0;

    while x >= 0.02 do
    begin
     x:=x-0.02;
     m:=m+1;
    end;
    writeln(m,' monet 0.02 zlotowych');
    m:=0;

    while x >= 0.01 do
    begin
     x:=x-0.01;
     m:=m+1;
    end;
    writeln(m,' monet 0.01 zlotowych');
    m:=0;
    readln(x);

end.

ale to niby nie jest to, jeszcze muszę jakąś tablice dodać, gdzie będę wpisywał jakie nominały są dostępne. Liczba monet nie ograniczona, ale okazało się, że ma wydawać resztę za pomocą dostępnych nominałów np mam tylko 5zl i 1 zl.

To jest w pascalu, a tu nie widzie osobnego działu tego języka więc tu piszę tu.
Z góry dzięki za pomoc

Pozdrawiam

1. Za wciśnięcie kombinacji klawiszy ctrl+c i ctrl+v powinien ci eksplodować monitor...

Delphi/Pascal
Na tym forum możesz wypowiadać się w sprawach Delphi oraz języka Pascal

Wiem ciężko go zauważyc, jest w końcu nad C/C++...

ok przeniosłem do delphi. a co do wklejania chyba łatwiej ocenić algorytm jeśli jest cały kod?
Pozdrawiam