Wpis z mikrobloga

Mam taki algorytm do napisania:

Wykorzystując programowanie dynamiczne powiedz, na ile sposobów można rozmienić banknot o
zadanym nominale n zakładając, że dysponujemy nieograniczoną liczbą monet o nominałach
podanych w tablicy M.

Jak ugryźć ten problem? Czytam artykuły o programowaniu dynamicznym i nic nie przychodzi mi do głowy.

#programowanie
#studbaza
  • 2
@Pawlis klasyczny problem na dynamiki :) Robisz sobie macierz n x m, przechodząc po kolumnach zwiększasz kwotę do rozmienienia, wraz z dojściem nowego wiersza dorzucasz do puli nowy nominał. Jeśli masz rozmienić kwotę x pulą nominałów {a1,a2,...,aj-1} i doszedł ci nowy nominał aj to pomyśl jak zmienia się liczba sposobów na wydanie kwoty z, wiedząc na ile sposobów można wydać kwotę x-a_j