From 50ebfcc340845052188eb0bc37978539cad74031 Mon Sep 17 00:00:00 2001 From: Ale46 Date: Sat, 13 Oct 2018 15:03:42 +0200 Subject: [dynamic-programming/it-IT] Add italian language for dynamic-programming --- it-it/dynamic-programming-it.html.markdown | 54 ++++++++++++++++++++++++++++++ 1 file changed, 54 insertions(+) create mode 100644 it-it/dynamic-programming-it.html.markdown (limited to 'it-it') diff --git a/it-it/dynamic-programming-it.html.markdown b/it-it/dynamic-programming-it.html.markdown new file mode 100644 index 00000000..963d096c --- /dev/null +++ b/it-it/dynamic-programming-it.html.markdown @@ -0,0 +1,54 @@ +--- +category: Algorithms & Data Structures +name: Dynamic Programming +contributors: + - ["Akashdeep Goel", "http://github.com/akashdeepgoel"] +translators: + - ["Ale46", "https://github.com/ale46"] +lang: it-it +--- + +# Programmazione dinamica + +## Introduzione + +La programmazione dinamica è una tecnica potente utilizzata per risolvere una particolare classe di problemi, come vedremo. L'idea è molto semplice, se hai risolto un problema con l'input dato, salva il risultato come riferimento futuro, in modo da evitare di risolvere nuovamente lo stesso problema. + +Ricordate sempre! +"Chi non ricorda il passato è condannato a ripeterlo" + +## Modi per risolvere questi problemi + +1. *Top-Down* : Inizia a risolvere il problema specifico suddividendolo. Se vedi che il problema è già stato risolto, rispondi semplicemente con la risposta già salvata. Se non è stato risolto, risolvilo e salva la risposta. Di solito è facile da pensare e molto intuitivo. Questo è indicato come Memoization. + +2. *Bottom-Up* : Analizza il problema e vedi l'ordine in cui i sotto-problemi sono risolti e inizia a risolvere dal sottoproblema banale, verso il problema dato. In questo processo, è garantito che i sottoproblemi vengono risolti prima di risolvere il problema. Si parla di programmazione dinamica. + +## Esempio di programmazione dinamica + +Il problema di "Longest Increasing Subsequence" consiste nel trovare la sottosequenza crescente più lunga di una determinata sequenza. Data una sequenza `S= {a1 , a2 , a3, a4, ............., an-1, an }` dobbiamo trovare il sottoinsieme più lungo tale che per tutti gli `j` e gli `i`, `j a[j] and LS[i]