dynamiczne programowanie i wykorzystanie macierzy

Question

Zawsze jestem zdezorientowany tym, jak dynamiczne programowanie wykorzystuje macierz do rozwiązania problemu. Rozumiem z grubsza, że ​​macierz służy do przechowywania wyników z poprzednich podproblemów, tak aby można ją było wykorzystać w późniejszym obliczaniu większego problemu.

Ale jak określić rozmiar matrycy i skąd wiemy, jaką wartość powinien reprezentować każdy wiersz/kolumna macierzy? tj. czy istnieje jak ogólna procedura konstruowania matrycy?

Na przykład, jeśli jesteśmy zainteresowani wprowadzeniem zmian dla kwoty S za pomocą monet o wartości c1, c2, .... cn, jaki powinien być wymiar macierzy, a co powinno być w każdej kolumnie/wierszu przedstawiać?

Pomocne będzie dowolne wskazówki kierunkowe. Dziękuję Ci!

Answer 1

Szorstkie kroki dla niektórych rodzajów problemów DP:

1. Znajdź rekurencyjną rozwiązanie

2. Jeśli jakieś pośrednie wyniki wywołań rekurencyjnych są obliczane ponownie i ponownie - zapamiętaj je i używać - Zbuduj tabelę odpowiednie wymiary - to jest zapamiętywanie

3. Ta tabela może być zwykle wypełniona od komórki początkowej do końcowej (wynik) - komórka po komórce, rząd po wierszu itd. ...

za zmiany problemu:

1. F (s) = F (s-C1) + F (s-C2) + ...

Postaraj się wypracować kompleksowe rozwiązanie rekurencyjne i ustalenia co stół jest potrzebny do przechowywania wyników pośrednich

Answer 2

tablica stosować roztwór DP jest prawie zawsze w oparciu o wymiarach przestrzeni stanów problemu - to znaczy, że prawidłowe wartości dla każdego z parametrów

Na przykład

fib[i+2] = fib[i+1] + fib[i] 

jest taka sama jak

def fib(i): 
    return fib(i-1)+fib(i-2] 

Można uczynić to bardziej widoczne poprzez wdrożenie memoization w swoim rekurencyjnych funkcji

def fib(i): 
    if(memo[i] == null) 
     memo[i] = fib(i-1)+fib(i-2) 
    return memo[i] 

Jeśli rekurencyjna funkcja ma parametry K, prawdopodobnie będziesz potrzebował matrycy wymiarowej K.

Answer 3

Ten rozdział wyjaśnia bardzo dobrze: http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf Na stronie 178 podaje kilka podejść do identyfikacji problemów podrzędnych, które umożliwiają zastosowanie programowania dynamicznego.