Programmation dynamique Recursion et une pincée de Memoization

Question

J'ai ce tableau massif de ints de 0-4 dans ce triangle. Je suis en train d'apprendre la programmation dynamique avec Ruby et voudrais une aide dans le calcul du nombre de chemins dans le triangle qui répondent à trois critères:

1. Vous devez commencer à l'un des points zéro de la ligne avec 70 éléments.
2. Votre chemin peut être directement au-dessus d'une ligne vous (s'il y a un certain nombre directement au-dessus) ou une ligne diagonale en tête à gauche. L'une de ces options est toujours disponible
3. La somme du chemin que vous prenez pour arriver à zéro sur la première ligne doit ajouter jusqu'à 140.

Exemple, commencer par le deuxième zéro dans la rangée inférieure. Vous pouvez passer directement à une ou à gauche en diagonale à 4. Dans les deux cas, le numéro que vous arrivez à doit être ajouté au compte courant de tous les chiffres que vous avez visités. Du 1 on peut voyager pour un 2 (en cours d'exécution total = 3) directement au-dessus ou au 0 (somme en cours d'exécution = 1) en diagonale à gauche.

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

Mais je comme devoirs:)

Je trouve plus facile de raisonner sur le problème des 'chemins de quand en partant du haut, et en suivant les règles l'inverse.

Cela signifie:

• un trajet partiel peut être le zéro en haut, ou un chemin d'accès partiel élargi
• les extensions d'un chemin partiel Pr, c sont, sauf r est la dernière ligne, où ils sont complets, l'union des
  • les extensions de Pr, c + P (r + 1), c
  • les extensions de Pr, c + P (r + 1), c + 1

La règle « somme » sélectionne simplement certains de tous les chemins complets.