# Exercices — Programmation Dynamique

## Exercice 1 — L'escalier

Vous souhaitez monter un escalier de `n` marches. À chaque étape, vous pouvez monter **1 marche** ou **2 marches**. Combien existe-t-il de façons différentes d'atteindre la n-ième marche ?

**Exemples :**
- `n = 1` : 1 façon (1)
- `n = 2` : 2 façons (1+1, 2)
- `n = 3` : 3 façons (1+1+1, 1+2, 2+1)
- `n = 4` : 5 façons

**1.** Calculez à la main le nombre de façons pour `n = 5`.

**2.** Quelle ressemblance observez-vous avec une suite mathématique vue dans le cours Récursivité ?

**3.** Écrivez la relation de récurrence pour `escalier(n)`.

**4.** Implémentez `escalier_memo(n)` en utilisant la mémoïsation.

**5.** Implémentez `escalier_bottom_up(n)` en utilisant un tableau.

**6.** Vérifiez que vos deux fonctions donnent les mêmes résultats pour `n` allant de 1 à 10.

---

## Exercice 2 — Rendu de monnaie revisité

On dispose de pièces de valeurs **[2, 5, 10]** (en centimes).

**1.** L'algorithme glouton peut-il rendre 6 centimes avec ce système ? Justifiez.

**2.** La programmation dynamique peut-elle rendre 6 centimes ? Justifiez.

**3.** Écrivez la fonction `rendu_bottom_up(pieces, somme)` (version bottom-up vue en cours) et testez-la avec :
   - `pieces = [2, 5, 10]`, `somme = 6`
   - `pieces = [1, 3, 4]`, `somme = 6`
   - `pieces = [1, 5, 6, 9]`, `somme = 11`

**4.** Modifiez la fonction pour qu'elle retourne non seulement le nombre de pièces, mais aussi la **liste des pièces utilisées** (comme la reconstruction dans le sac à dos).

---

## Exercice 3 — Sac à dos : à la main et en code

On dispose des objets suivants, avec un sac de capacité **6 kg** :

| Objet | Poids | Valeur |
|-------|-------|--------|
| A | 1 kg | 2 |
| B | 2 kg | 5 |
| C | 3 kg | 8 |
| D | 4 kg | 9 |

**1.** Remplissez à la main le tableau `tableau[i][w]` pour `i` de 0 à 4 et `w` de 0 à 6.

**2.** Quelle est la valeur maximale atteignable ?

**3.** En remontant le tableau, déterminez quels objets sont dans la solution optimale.

**4.** Vérifiez vos réponses en exécutant `sac_reconstruction(objets, 6)`.

---

## Exercice 4 — Triangle de Pascal ★

Le **triangle de Pascal** est construit selon la règle suivante :
- Les bords valent toujours 1
- Chaque case intérieure est la somme des deux cases au-dessus d'elle

```
Ligne 0 :     1
Ligne 1 :    1 1
Ligne 2 :   1 2 1
Ligne 3 :  1 3 3 1
Ligne 4 : 1 4 6 4 1
```

**1.** Écrivez la relation de récurrence : `pascal(ligne, col) = ?`

**2.** Implémentez `triangle_pascal(n)` par programmation dynamique bottom-up, qui retourne les `n` premières lignes du triangle sous forme de liste de listes.

**3.** Vérifiez que `triangle_pascal(5)` donne `[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]`.

**4.** *(Bonus)* La somme des éléments de la ligne `n` est-elle liée à une valeur vue dans ce chapitre ?

---

Auteur : Florian Mathieu

Licence CC BY NC

<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/"><img alt="Licence Creative Commons" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" /></a> <br />Ce cours est mis à disposition selon les termes de la <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International</a>.