Quando hai usato la programmazione dinamica sul campo?

Question

Quando hai mai applicato direttamente i concetti di programmazione dinamica per risolvere un problema sul campo ? A volte non è chiaro come possa essere applicato quando lo si utilizza per risolvere un'istanza inventata del problema con lo zaino .

Answer 1

Probabilmente è molto più comune usare memoization per risolvere problemi sul campo, dal momento che è applicabile a una serie più ampia di problemi. DP è davvero richiesto solo quando ci sono molti sotto-problemi sovrapposti, come nel calcolo dei numeri di fibonacci (il modo più difficile) o dei numeri primi (il modo più efficiente).

Per inciso, la pagina a cui hai effettuato il collegamento ha un elenco di algoritmi che utilizzano DP .