programmazione dinamica e l'uso di matrici

Question

Sono sempre confuso su come la programmazione dinamica utilizza la matrice per risolvere un problema. Capisco grosso modo che la matrice sia utilizzata per memorizzare i risultati dei precedenti sottoproblemi, in modo che possa essere utilizzata nel calcolo successivo di un problema più grande.

Ma come si determina la dimensione della matrice e come si conosce il valore che ogni riga/colonna della matrice deve rappresentare? cioè, c'è una procedura generica per costruire la matrice?

Ad esempio, se siamo interessati a apportare modifiche per la quantità di denaro S utilizzando monete di valore c1, c2, .... cn, quale dovrebbe essere la dimensione della matrice e cosa dovrebbe ogni colonna/riga rappresentare?

Qualsiasi guida direzionale aiuterà. Grazie!

Answer 1

passi grezzi per alcuni tipi di problemi DP:

1. trovare una soluzione ricorsiva

2. Se alcuni risultati intermedi di chiamate ricorsive vengono calcolati ancora e ancora - li e l'uso ricordare - costruire una tabella con dimensioni appropriate - è la memoazione

3. Questa tabella di solito può essere riempita dalla cella iniziale alla finale (risultato) - cella per cella, riga per riga e così via ...

Per problema del cambiamento:

1. F (s) = F (s-c1) +

Prova di elaborare soluzione ricorsiva completa e determinare (s-c2) + F ... quale tabella è necessaria per memorizzare i risultati intermedi

Answer 2

un array utilizzata da una soluzione DP è quasi sempre in base alle dimensioni dello spazio degli stati del problema - cioè, i valori validi per ciascuno dei suoi parametri

Per esempio

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

è lo stesso di

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

Si può fare questo è più evidente implementando Memoizzazione nelle funzioni ricorsive

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

Se la funzione ricorsiva ha dei parametri K, probabilmente avrai bisogno di una matrice K-dimensionale.

Answer 3

Questo capitolo lo spiega molto bene: http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf A pagina 178 fornisce alcuni approcci per identificare i sotto problemi che consentono di applicare la programmazione dinamica.