Dynamic programming

This repository contains step-by-step introductory examples to dynamic programming.

Each folder includes an example divided into three steps:

step_1.py: Minimum finding. This step directly implements the Bellman equation using simple recursion without memoization. To ensure reasonable runtime, it may be necessary to reduce the problem size.
step_2.py: Memoization implementation. Allows solving larger problems efficiently.
step_3.py: Minimizer finding. Here, we store the necessary information in the memo to enable the reconstruction of the optimal solution.

Programmation dynamique

Exemples pas à pas conçus pour introduire la programmation dynamique dans la prépa Lachenal.

Chaque dossier comprend un exemple divisé en trois étapes :

step_1.py : Recherche du minimum. Cette étape met en œuvre directement l'équation de Bellman en utilisant une récursion simple sans mémoïsation. Pour garantir un temps d'exécution raisonnable, il peut être nécessaire de réduire la taille du problème.
step_2.py : Mise en place de la mémoïsation. Permet de résoudre efficacement des problèmes plus grands.
step_3.py : Recherche du minimiseur. Nous stockons les informations nécessaires dans le memo pour pouvoir reconstruire la solution optimale.