---
tags: corrTD, info, progdyna, 2526
---
<center>TD4 : programmation dynamique</center>
===
> :books: Documents de base : le [cours](http://demeslay.maths.free.fr/fichiers/info/2_ProgrammationDynamique_cours.pdf) et le [TD3](http://demeslay.maths.free.fr/fichiers/info/TD4_progdyna.pdf). [color=red]
[TOC]
## Exercice 1 : Somme dans une pyramide
* **Q2.** On traduit la formulation mathématique du problème : la base forme les cas d'arrêt et sinon on effectue des appels récursifs sur les deux voisins du dessous.
```python=
def somme(p: [[int]], i: int, j: int) -> int:
""" Renvoie la somme maximale obtenue dans la pyramide p en partant
de la position (i, j). """
if i == 0: # Si on se trouve à la base
return p[i][j]
else:
gauche = somme(p, i-1, j) # Somme maximale en prenant l'élément en
# dessous à gauche.
droite = somme(p, i-1, j+1) # Idem avec celui en dessous à droite.
if gauche < droite:
return p[i][j] + droite
else:
return p[i][j] + gauche
```
* **Q3.** Il faut partir du sommet de la pyramide donc effectuer l'appel `somme(p, len(p)-1, 0)`.
* **Q4.** On recalcule la même chose plusieurs fois lors des appels récursifs ce qui entraîne une perte de temps.
Par exemple, avec la pyramide donnée en exemple, en partant du sommet, après 13, on va calculer ce qu'il y a sous 12 et sous 18, alors qu'après 9, on va calculer ce qu'il y a sous 18 (même si on l'a déjà fait) et sous 21.
:::info
:bulb: Pour y remédire, on va stocker les résultats intermédiaires (dans une liste ou un dictionnaire), c'est le procédé de mémoïsation.
:::
* **Q5.** On reprend la fonction précédente mais on y ajoute de la mémoire.
On commence par créer un dictionnaire vide puis, avant l'appel récursif, on teste si la valeur est déjà en mémoire : si oui on la prend, sinon on la calcule et on la stocke pour ne pas avoir à la recalculer si on doit s'en resservir.
```python=
MEMO = dict() # Pour stockage résultats intermédiaires
def somme_memo(p: [[int]], i: int, j: int) -> int:
""" Renvoie la somme maximale obtenue dans la pyramide p en partant
de la position (i, j). """
if i == 0: # Si on se trouve à la base
return p[i][j]
else:
if (i-1, j) in MEMO: # test si en bas à gauche déjà calculé
gauche = MEMO[(i-1, j)]
else: # sinon on le calcule et le stocke
gauche = somme_memo(p, i-1, j)
MEMO[(i-1, j)] = gauche
# idem en bas à droite
if (i-1, j+1) in MEMO:
droite = MEMO[(i-1, j+1)]
else:
droite = somme_memo(p, i-1, j+1)
MEMO[(i-1, j+1)] = droite
# fin comme précédemment
if gauche < droite:
return p[i][j] + droite
else:
return p[i][j] + gauche
```
* **Q6.** C'est une copie de la pyramide mais sous la forme d'un dictionnaire dont les clés sont des couples d'entiers donnant les coordonnées d'une case et la valeur associée le nombre dans cette case.
* **Q7.** C'est comme dans la **Q2** :
```python=6
gauche = memo[(i-1, j)]
droite = memo[(i-1, j+1)]
```
* **Q8.** On parcourt une unique fois chaque élément de la pyramide (double boucle en `i` et `j`) et à chaque fois, trois affectations, une comparaison et une addition. Ainsi la complexité est en $O\Bigl(\tfrac{n(n+1)}{2}\Bigr)$ (= nb éléments de la pyramide de hauteur n), i.e. $O(n^2)$.
## Exercice 2 : coefficients binomiaux
* **Q1.** _Sous-structure optimale_ : pour calculer un coefficient binomial $\binom{n}{k}$ par cette méthode, on a besoin de calculer ceux de la forme $\binom{m}{j}$ avec $m < n$.
_Chevauchement des sous-problèmes_ : on va utiliser plusieurs fois les mêmes valeurs. Par exemple $\binom{4}{2}$ servira à la fois pour calculer $\binom{5}{2}$ et pour $\binom{5}{3}$.
* **Q2.** Donnons d'abord une version sans mémoïsation traduisant juste l'énoncé.
```python=
def binom(n: int, k: int) -> int:
""" Renvoie la valeur de k parmi n. """
if k == 0 or k == n:
return 1
else:
# Formule de Pascal
return binom(n-1, k-1) + binom(n-1, k)
```
On rajoute alors la partie mémoïsation avec un stockage des résultats intermédiaires et un test pour savoir si on les a déjà calculés ou non.
```python=
MEMO = dict()
def binom_desc(n: int, k: int) -> int:
""" Renvoie valeur de k parmi n. """
if k == 0 or k == n:
return 1
if (n, k) in MEMO:
return MEMO[(n, k)]
else:
# Formule de Pascal
coeff = binom_desc(n-1, k-1) + binom_desc(n-1, k)
MEMO[(n, k)] = coeff
return coeff
```
* **Q3.** On traduit ce que l'on fait habituellement à la main pour calculer les coefficients binomiaux.
```python=
def binom_asc(n: int, k: int) -> int:
""" Renvoie la valeur de k parmi n. """
triangle = [[1]]
for i in range(1, n+1):
# On calcule les j parmi i.
ligne = [1] # 0 parmi i vaut 1
for j in range(1, i):
ligne.append(triangle[i-1][j-1] + triangle[i-1][j]) # Pascal
ligne.append(1) # i parmi i vaut 1
triangle.append(ligne)
return triangle[n][k]
```