## Exemple : Fibonnaci

# Rappel de la fonction mémoïsée
def fibo_memo(n):
    memo = {}
    def aux(i):
        if i in memo:
            return memo[i]
        else:
            if i <= 1:
                memo[i] = 1
                return memo[i]
            else:
                memo[i] = aux(i-1) + aux(i-2)
                return memo[i]
    return aux(n)

# Dépendances
# i dépend de i-1 et i-2

# Version en Prog Dyn ascendantes
def fibo(n):
    if n < 2:
        return 1
    a = 1
    b = 1
    for i in range(2, n+1):
        # Au début de la boucle, a = fibo(i-2) et b=fibo(i-1)
        ancien_a = a
        ancien_b = b
        a = ancien_b
        b = ancien_a + ancien_b
        # À la fin de la boucle, a = fibo(i-1) et b = fibo(i)
    return b

## Exercice 1 : Grenouille

# Rappel : fonction récursive
def grenouille_memo(hauteurs):
    n = len(hauteurs)
    memo = {}
    def aux(depart):
        if depart in memo:
            return memo[depart]
        if depart == n-1:
            memo[depart] = 0
            return memo[depart]
        if depart == n-2:
            memo[depart] = abs(hauteurs[n-2] - hauteurs[n-1])
            return memo[depart]
        saut1 = abs(hauteurs[depart] - hauteurs[depart + 1])
        saut2 = abs(hauteurs[depart] - hauteurs[depart + 2])
        reste1 = aux(depart + 1)
        reste2 = aux(depart + 2)
        memo[depart] = min(saut1 + reste1, saut2 + reste2)
        return memo[depart]
        # Fin de la fonction aux
    return aux(0)

# Exemple de liste de hauteurs
exemple_hauteurs = [6, 7, 4, 8, 2, 9, 0]

# Version en prog dyn ascendante
def grenouille(hauteurs):
    pass # À faire

## Exercice 2 : Pyramide

# Rappel : fonction récursive
def pyramide_memo(pyr):
    hauteur = len(pyr)
    memo = {}
    def aux (ligne, colonne):
        if (ligne, colonne) in memo :
            return memo[(ligne, colonne)]
        if ligne == hauteur - 1:
            memo[(ligne, colonne)] = pyr[ligne][colonne]
            return memo[(ligne, colonne)]
        else:
            nombre = pyr[ligne][colonne]
            choix_gauche = nombre + aux(ligne+1, colonne-1)
            choix_droite = nombre + aux(ligne+1, colonne+1)
            memo[(ligne, colonne)] = max(choix_gauche, choix_droite)
            return memo[(ligne, colonne)]
    return aux(0, 0)

# Exemple de pyramide
ex_pyramide_1 = [
              { 0: 3 },
           { -1: 5 , 1: 4},
         {-2: 1, 0: 5, 2: 9},
      {-3: 2, -1: 6, 1: 5, 3: 3},
    {-4: 5, -2: 8, 0: 9, 2: 7, 4: 9}
    ]


# Version en programmation dynamique ascendante
def somme_pyramide(pyr):
    pass # À faire

## Exercice 3 : Distance d'édition

# Rappel : fonction mémoïsée
def memo_levenshtein(u, v):
    memo = {}
    def aux(i, j):
        if (i,  j) in memo:
            return memo[(i, j)]
        if i == 0:
            memo[(i, j)] = j
            return memo[(i, j)]
        if j == 0:
            memo[(i, j)] = i
            return memo[(i, j)]
        if u[i-1] == v[j-1]:
            memo[(i, j)] = aux(i-1, j-1)
            return memo[(i, j)]
        memo[(i, j)] = 1 + min(aux(i-1, j), aux(i, j-1), aux(i-1, j-1))
        return memo[(i, j)]
        # Fin de la fonction aux
    aux(len(u), len(v))
    return memo

# Version en programmation dynamique ascendante
def levenshtein(u, v):
    pass # À faire