Oui, la récursion avec cache, c'est assez similaire à la programmation dynamique.
La différence c'est qu'en version récursive, on part du problème initial pour descendre dans l'arbre des appels récursifs alors qu'avec la programmation dynamique, on dérécursifie l'algorithme en partant des feuilles de l'arbre et en remontant à la racine (le problème initial).
En général, un algorithme en programmation dynamique est un peu plus rapide que sa version récursive avec cache (car pas de récursion et on utilise en général un tableau dont l'accès est plus rapide qu'un cache qui est en général implémenté par un hashset).
C'est aussi parfois beaucoup plus économe en mémoire.
[^] # Re: Jour 7
Posté par Guillaume.B . En réponse au journal Advent of Code 2025. Évalué à 3.
Oui, la récursion avec cache, c'est assez similaire à la programmation dynamique.
La différence c'est qu'en version récursive, on part du problème initial pour descendre dans l'arbre des appels récursifs alors qu'avec la programmation dynamique, on dérécursifie l'algorithme en partant des feuilles de l'arbre et en remontant à la racine (le problème initial).
En général, un algorithme en programmation dynamique est un peu plus rapide que sa version récursive avec cache (car pas de récursion et on utilise en général un tableau dont l'accès est plus rapide qu'un cache qui est en général implémenté par un hashset).
C'est aussi parfois beaucoup plus économe en mémoire.