Ricorsione Programmazione Dinamica e una spolverata di Memoizzazione

Question

Ho questa massiccia serie di int da 0-4 in questo triangolo. Sto cercando di imparare la programmazione dinamica con Ruby e vorrei un po 'di assistenza nel calcolo del numero di percorsi nel triangolo che soddisfano tre criteri:

1. deve iniziare in uno dei punti zero nella fila con 70 elementi.
2. Il tuo percorso può essere direttamente sopra di voi una riga (se v'è un numero direttamente sopra) o una riga verso l'alto in direzione diagonale verso sinistra. Una di queste opzioni è sempre disponibile
3. La somma del percorso si prende per raggiungere lo zero sulla prima riga deve aggiungere fino a 140.

Esempio, inizia alla seconda zero nella fila inferiore. È possibile passare direttamente fino a quello o diagonale sinistra alla 4. In entrambi i casi, il numero si arriva a deve essere aggiunto al conteggio di tutti i numeri che hai visitato. Dal 1 si può viaggiare a una (in esecuzione sum = 3) 2 direttamente al di sopra o al 0 (in esecuzione sum = 1) in diagonale verso sinistra.

0  
41  
302  
2413  
13024  
024130  
4130241  
30241302  
241302413  
1302413024  
02413024130  
413024130241  
3024130241302  
24130241302413  
130241302413024  
0241302413024130  
41302413024130241  
302413024130241302  
2413024130241302413  
13024130241302413024  
024130241302413024130  
4130241302413024130241  
30241302413024130241302  
241302413024130241302413  
1302413024130241302413024  
02413024130241302413024130  
413024130241302413024130241  
3024130241302413024130241302  
24130241302413024130241302413  
130241302413024130241302413024  
0241302413024130241302413024130  
41302413024130241302413024130241  
302413024130241302413024130241302  
2413024130241302413024130241302413  
13024130241302413024130241302413024  
024130241302413024130241302413024130  
4130241302413024130241302413024130241  
30241302413024130241302413024130241302  
241302413024130241302413024130241302413  
1302413024130241302413024130241302413024  
02413024130241302413024130241302413024130  
413024130241302413024130241302413024130241  
3024130241302413024130241302413024130241302  
24130241302413024130241302413024130241302413  
130241302413024130241302413024130241302413024  
0241302413024130241302413024130241302413024130  
41302413024130241302413024130241302413024130241  
302413024130241302413024130241302413024130241302  
2413024130241302413024130241302413024130241302413  
13024130241302413024130241302413024130241302413024  
024130241302413024130241302413024130241302413024130  
4130241302413024130241302413024130241302413024130241  
30241302413024130241302413024130241302413024130241302  
241302413024130241302413024130241302413024130241302413  
1302413024130241302413024130241302413024130241302413024  
02413024130241302413024130241302413024130241302413024130  
413024130241302413024130241302413024130241302413024130241  
3024130241302413024130241302413024130241302413024130241302  
24130241302413024130241302413024130241302413024130241302413  
130241302413024130241302413024130241302413024130241302413024  
0241302413024130241302413024130241302413024130241302413024130  
41302413024130241302413024130241302413024130241302413024130241  
302413024130241302413024130241302413024130241302413024130241302  
2413024130241302413024130241302413024130241302413024130241302413  
13024130241302413024130241302413024130241302413024130241302413024  
024130241302413024130241302413024130241302413024130241302413024130  
4130241302413024130241302413024130241302413024130241302413024130241  
30241302413024130241302413024130241302413024130241302413024130241302  
241302413024130241302413024130241302413024130241302413024130241302413  
1302413024130241302413024130241302413024130241302413024130241302413024  
02413024130241302413024130241302413024130241302413024130241302413024130  

Answer 1

I come compiti a casa:)

Trovo più facile ragionare su problema dei 'percorsi' quando partendo dall'alto, e seguendo le regole viceversa.

Ciò significa:

• un percorso parziale può essere superiore a zero, o un percorso parziale esteso
• le estensioni di un percorso parziale Pr, c sono, a meno che r è l'ultima fila, in cui sono complete, l'unione di
  • le estensioni di Pr, c + P (r + 1), c
  • le estensioni di Pr, c + P (r + 1), c + 1

La regola 'somma' seleziona solo alcuni dei tutti i percorsi completi.