Programmation Dynamique Principe

Introduction

La programmation dynamique est une technique algorithmique utilisée pour résoudre des problèmes complexes en les décomposant en sous-problèmes plus simples et en mémorisant les résultats des sous-problèmes pour éviter les calculs redondants. Cette approche est particulièrement utile pour les problèmes d'optimisation où des solutions récurrentes sont nécessaires.

Notions Fondamentales

1. Définition

La programmation dynamique est une méthode pour résoudre des problèmes de manière récursive, mais en stockant les résultats intermédiaires afin d'éviter de recalculer les mêmes sous-problèmes plusieurs fois. Cela se fait généralement en utilisant un tableau ou une structure de données similaire.

2. Propriétés

• Décomposition : Le problème est décomposé en sous-problèmes plus simples.
• Optimalité : La solution globale est construite à partir des solutions optimales des sous-problèmes.
• Mémorisation : Les résultats des sous-problèmes sont mémorisés pour éviter des calculs redondants.

3. Applications

• Fibonacci : Calcul des nombres de Fibonacci.
• Problème du sac à dos : Optimisation de la sélection d'objets pour maximiser la valeur tout en respectant une contrainte de poids.
• Édition de chaîne : Calcul de la distance d'édition entre deux chaînes.

Principe de Fonctionnement

4. Mémorisation (Top-Down)

Dans l'approche de mémorisation, nous utilisons la récursivité pour résoudre les sous-problèmes, mais nous mémorisons les résultats pour les réutiliser.

Exemple : Calcul des nombres de Fibonacci

function fibonacci(n, memo = {}) {
    if (n in memo) return memo[n]; // Retourne le résultat mémorisé si déjà calculé
    if (n <= 1) return n;
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo); // Mémorise le résultat
    return memo[n];
}

console.log(fibonacci(10)); // Output: 55

5. Programmation Dynamique (Bottom-Up)

Dans l'approche de programmation dynamique, nous construisons la solution à partir des sous-problèmes les plus simples jusqu'au problème principal, souvent en utilisant un tableau.

Exemple : Calcul des nombres de Fibonacci

function fibonacci(n) {
    if (n <= 1) return n;
    let fib = [0, 1]; // Tableau pour mémoriser les résultats
    for (let i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2]; // Calcule le résultat et le mémorise
    }
    return fib[n];
}

console.log(fibonacci(10)); // Output: 55

Exercice avec un Exemple Amusant

Le Château de la Princesse

Histoire :

Imagine que tu es un chevalier et que tu dois sauver une princesse dans un château. Le château est rempli de salles et chaque salle a des portes qui mènent à d'autres salles. Certaines portes sont plus difficiles à franchir que d'autres et certaines salles contiennent des trésors. Tu veux atteindre la salle de la princesse avec le plus de trésors possible, mais tu ne veux pas repasser par les mêmes salles plusieurs fois inutilement.

Explication :

1. Décomposition :
   • Chaque salle représente un sous-problème.
   • Franchir une porte représente résoudre un sous-problème.
2. Mémorisation :
   • Tu mémorises les salles déjà visitées et les trésors collectés pour ne pas recalculer ces informations.
3. Optimalité :
   • À chaque étape, tu choisis la porte qui mène à la salle avec le maximum de trésors mémorisés.