Algoritmi - Programmazione Dinamica

Salve a tutti. Pochi giorni fa ho preso parte ad una delle lezioni preparatorie alla selezione regionale delle olimpiadi di informatica, organizzate dalla mia scuola in collaborazione col dipartimento di Informatica dell' università de L'Aquila.

Il professore quel giorno ha spiegato la programmazione dinamica per l'ottimizzazione di algoritmi ricorsivi. Non avendo capito immediatamente l'argomento trattato ho fatto qualche ricerca in internet dove veniva detto che questo tipo di programmazione si basa più sull'approccio bottom-up che sul top-down. Ho provato ad utilizzare questa tecnica di programmazione riuscendo a creare solo una versione quasi istantantea della funzione ricorsiva della successione di fibonacci Fn = F(n-1)+F(n-1).

Vorrei però capire meglio il funzionamento di questa tecnica perchè mi sarebbe molto utile per risolvere alcuni problemi di projecteuler.net. Qualcuno riesce a darmi una spiegazione semplice?

Ciao!
Ti avverto fin da subito che di programmazione dinamica non me ne intendo gran che.
Tuttavia il concetto che stalla alle base è che se risolvo un sotto-problema conviene salvarlo in modo tale da averlo già risolto per il futuro.

Qui puoi trovare una pagina che avevo scritto tempo fa: xbarbox.pierotofy.it/…
Il problema dello zaino è un ottimo esempio un po' più avanzato di Fibonacci per capire bene la programmazione dinamica.

A proposito di project euler c'è un bellissimo esempio sulla congettura di collatz projecteuler.net/…

Questo è un esempio valido per la programmazione dinamica in quanto un sotto problema può tornare utile a un problema di "livello superiore".
Infatti, se definisco collatz(n) come la lunghezza della sequenza di collatz a partire da n, posso definire il problema ricorsivamente in questo modo:

se n pari => collatz(n) = 1 + collatz(n/2)
se n dispari => collatz(n) = 1 + collatz(3*n + 1)
con caso base collatz(1) = 1

Per esempio collatz(16) è istantaneo da calcolare se conosco collatz(8) in quanto collatz(16) = 1 + collatz(8).
Quindi un metodo rapido consiste nel salvarti in un vettore tutti i risultati di collatz(i) in posizione i del vettore.

Spero di essere stato chiaro e di aiuto! In bocca al lupo per le olimpiadi!

E siamo in due

Quanto odio gli esercizi del tipo:

#include <stdio.h>

int max(int a, int b) {
	if(a > b) return a;
	return b;
}
int f(int a, int b) {
	if (a == b) return b;
	if (a < 0) return -b; 
	return max(f(a-1, 2*b), f(a-1, 2*b+1));
}
void main() {
	printf("%d", f(8, 0));
}

Per quanto riguarda il problema 14 di projecteuler l'ho già debitamente risolto senza utilizzare la programmazione dinamica. Invece devo utilizzarla per risolvere il problema 15, projecteuler.net/…, dato che ho ottenuto ricorsivamente la soluzione al problema verificando l'esempio riportato, tuttavia, la durata dell'esecuzione per la risoluzione del problema vero e proprio è veramente lunga.