Programmation dynamique (corrections)

def revenu_barre(n):    
   prix = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30] # Indice 0 inutilisé
   if n == 0:
        return 0 # Cas de base: revenu pour une barre de longueur 0 est 0
    
   r = float('-inf')
   for i in range(1, n + 1):
       # r = max(r, prix[longueur_du_premier_morceau] + revenu_max_du_reste)
       r = max(r, prix[i] + revenu_barre(n - i)) 
   return r

def revenu_barre_dyn_desc(n):
    prix = [0, 1, 6, 9, 11, 12, 19, 20, 23, 24, 26]
    mem = [-1] * (n + 1) # -1 indique que le revenu n'a pas encore été calculé
    
    def r_mem(k):
        if k == 0:
            return 0
        
        # 1. Vérification : Si déjà calculé, retourner le résultat mémorisé
        if mem[k] != -1:
            return mem[k]
        
        # 2. Calcul : Sinon, calculer le revenu maximal
        r_max = float('-inf')
        for i in range(1, k + 1):
            # Utiliser r_mem(k - i) pour l'appel récursif (mémorisé)
            r_max = max(r_max, prix[i] + r_mem(k - i))
        
        # 3. Mémorisation : Stocker le résultat avant de le retourner
        mem[k] = r_max
        return r_max
        
    return r_mem(n)

def revenu_barre_dyn_asc(n):
    prix = [0, 1, 6, 9, 11, 12, 19, 20, 23, 24, 26]
    tab = [0] * (n + 1) # tab[i] stockera le revenu maximal ri
    # tab[0] est déjà à 0 (r0 = 0)
    
    # On itère de la longueur m=1 à m=n
    for m in range(1, n + 1):
        r_max = float('-inf')
        # On calcule le revenu maximal pour la longueur m
        for i in range(1, m + 1):
            # Calcul r_max = max(pi + r_m-i)
            # tab[m-i] contient le revenu r_m-i déjà calculé
            r_max = max(r_max, prix[i] + tab[m - i]) 
            
        tab[m] = r_max
        
    return tab[n]

      [3]
     [1, 2]
    [4, 5, 9]
   [3, 6, 2, 1]

def est_chemin(ch, p):
    # Règle 1: La longueur doit correspondre au nombre de niveaux
    if len(ch) != len(p):
        return False
    
    # Règle 2: Doit commencer par 0
    if ch[0] != 0:
        return False
        
    # Règle 3: Vérification du déplacement
    for i in range(len(ch) - 1):
        a = ch[i]
        b = ch[i+1]
        
        # Le nouvel indice (b) doit être a ou a + 1
        if not (b == a or b == a + 1):
            return False
            
    # Si toutes les règles sont respectées
    return True

# Tests :
# est_chemin([0,1,2,2], ex2) -> True
# est_chemin([0, 0, 0, 2], ex2) -> False (problème à l'étape 3, 0 -> 2)

def score(ch, p):
    s = 0
    # Parcourt chaque niveau (i) de la pyramide et l'indice (j) du chemin
    for i in range(len(p)):
        j = ch[i]
        s += p[i][j]
    return s

# Test :
# score([0,1,1,1,2], ex1) -> 4 + 2 + 5 + 1 + 3 = 15

def calcule_score_max(p, i=0, j=0):
    # Cas de base (dernier niveau)
    if i == len(p) - 1:
        return p[i][j]
    
    # Cas récursif: valeur du niveau courant + max des scores des deux sous-pyramides
    gauche = calcule_score_max(p, i + 1, j)
    droite = calcule_score_max(p, i + 1, j + 1)
    
    return p[i][j] + max(gauche, droite)

# Le score maximal est obtenu par calcule_score_max(ex1)

def pyramide_nulle(n):
    pyramide = []
    for i in range(n):
        # Chaque niveau i a une taille de i + 1
        pyramide.append([0] * (i + 1)) 
    return pyramide

# Exemple: pyramide_nulle(4) -> [[0],[0,0],[0,0,0],[0,0,0,0]]

def prog_dyn(p):
    n = len(p)
    if n == 0:
        return 0
        
    # Création de la pyramide des scores maximaux (s)
    # L'approche ascendante utilise souvent un tableau de la taille des données d'entrée.
    # Pour simplifier, on peut initialiser s avec la structure de p (ou une copie)
    s = [list(niveau) for niveau in p] 
    
    # On commence par l'avant-dernier niveau et on remonte jusqu'au sommet (niveau 0)
    for i in range(n - 2, -1, -1):
        # Pour chaque élément (j) du niveau i
        for j in range(len(s[i])):
            
            # Application de la relation de récurrence (score_max)
            # p[i][j] + max(score_max(i+1, j), score_max(i+1, j+1))
            
            # Les valeurs score_max(i+1, ...) sont déjà calculées au niveau i+1 de s.
            max_suivants = max(s[i+1][j], s[i+1][j+1])
            
            # Mise à jour du score maximal pour l'élément (i, j)
            s[i][j] = p[i][j] + max_suivants
            
    # Le score maximal pour la pyramide entière est au sommet
    return s[0][0]

# Test : prog_dyn(ex1) -> 4 + max(6, 2) + ... -> 23

def rendu_monnaie_solution(pieces, s):
    """
    Renvoie la liste minimale de pièces pour faire la somme s 
    avec le système 'pieces' (Programmation Dynamique).
    """
    # Initialisation au pire cas (n pièces de 1)
    nb = [n for n in range(s + 1)]          # Nombre minimal de pièces
    sol = [[1] * n for n in range(s + 1)] # Liste des pièces utilisées pour chaque somme
    sol[0] = []

    for n in range(1, s + 1):
        for p in pieces:
            if p <= n:
                # Si prendre la pièce p mène à un meilleur nombre total de pièces
                if 1 + nb[n - p] < nb[n]:
                    nb[n] = 1 + nb[n - p]
                    
                    # Mise à jour de la solution : 
                    # Prendre la solution optimale pour le reste (n-p) et ajouter la pièce p
                    sol[n] = sol[n - p].copy() 
                    sol[n].append(p)
                    
    # Retourne la solution optimale pour la somme s
    return sol[s]

def fibonacci(n):
    if n < 0:
        raise ValueError("n doit être positif")
    if n == 0:
        return 0
    
    # Création du tableau de mémorisation F[0] à F[n]
    f = [0] * (n + 1)
    
    # Initialisation des cas de base
    # f[0] = 0 (déjà fait par l'initialisation)
    f[1] = 1
    
    # Calcul itératif de F[2] jusqu'à F[n]
    for i in range(2, n + 1):
        # f[i] = f[i-2] + f[i-1] (Approche ascendante)
        f[i] = f[i - 2] + f[i - 1]
        
    return f[n]

def affiche(s1, s2, sc):
    """Affiche la table des scores d'alignement de manière formattée."""
    
    # 1. Affichage de l'en-tête de colonne (s2)
    print(" ", end="") # Espace pour l'angle supérieur gauche
    for c in s2:
        print('{:>3}'.format(c), end="")
    print() # Retour à la ligne pour le début du tableau
    
    # 2. Affichage des lignes (s1 et scores)
    for i in range(len(sc)): # i va de 0 à len(s1)
        
        # Affichage du caractère de début de ligne (s1[i-1] ou espace/tirets pour la ligne 0)
        if i > 0:
            print('{:>3}'.format(s1[i - 1]), end="")
        else:
            print(" ", end="") # Espace pour la première ligne (index 0)

        # Affichage des scores de la ligne
        for v in sc[i]:
            print('{:>3}'.format(v), end="")
        print() # Retour à la ligne pour la ligne suivante
        
# Exemple d'utilisation (avec les données de l'exercice 5) :
# s1 = "CHAT", s2 = "CAT", sc = [[0,-1,-2,-3],[-1,1,0,-1],[-2,0,0,0],[-3,-1,1,0],[-4,-2,0,2]]
# affiche(s1, s2, sc)
#     C  A  T
#   0 -1 -2 -3
# C -1  1  0 -1
# H -2  0  0  0
# A -3 -1  1  0
# T -4 -2  0  2

def aligne_solution(s1, s2):
    n1, n2 = len(s1), len(s2)
    sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]
    # sol[i][j] stockera le couple (align_s1, align_s2) optimal jusqu'à s1[i-1], s2[j-1]
    sol = [[("", "")] * (n2 + 1) for _ in range(n1 + 1)]

    # Initialisation des bords (Gaps)
    for i in range(1, n1 + 1):
        sc[i][0] = -i
        sol[i][0] = (s1[0:i], "-" * i) # Alignement de s1[0:i] avec des gaps
    for j in range(1, n2 + 1):
        sc[0][j] = -j
        sol[0][j] = ("-" * j, s2[0:j]) # Alignement de s2[0:j] avec des gaps

    # Reste du tableau
    for i in range(1, n1 + 1):
        for j in range(1, n2 + 1):
            
            # Options possibles et leurs scores
            score_gap_s1 = -1 + sc[i - 1][j]           # Gap dans s2 (vertical)
            score_gap_s2 = -1 + sc[i][j - 1]           # Gap dans s1 (horizontal)
            
            # Match ou Mismatch
            sim_score = 1 if s1[i - 1] == s2[j - 1] else -1
            score_diag = sim_score + sc[i - 1][j - 1] # Diagonale

            # Détermination du score maximal et de la solution correspondante
            
            # 1. Initialisation avec le meilleur score connu (souvent un gap)
            s_max = score_gap_s1
            (x, y) = sol[i - 1][j]
            sol[i][j] = (x + s1[i - 1], y + "-") # Aligne s1[i-1] avec un gap

            # 2. Test du Gap dans s1
            if score_gap_s2 > s_max:
                s_max = score_gap_s2
                (x, y) = sol[i][j - 1]
                sol[i][j] = (x + "-", y + s2[j - 1]) # Aligne s2[j-1] avec un gap

            # 3. Test de la Diagonale (Match ou Mismatch)
            if score_diag > s_max:
                s_max = score_diag
                (x, y) = sol[i - 1][j - 1]
                sol[i][j] = (x + s1[i - 1], y + s2[j - 1]) # Aligne les deux caractères

            sc[i][j] = s_max

    # Retourne le score et le couple de chaînes alignées
    return sc[n1][n2], sol[n1][n2]

sim = {
    'A': {'A': 10, 'G': -1, 'C': -3, 'T': -4},
    'G': {'A': -1, 'G': 7,  'C': -5, 'T': -3},
    'C': {'A': -3, 'G': -5, 'C': 9,  'T': 0},
    'T': {'A': -4, 'G': -3, 'C': 0,  'T': 8}
}
gap = -5 # Coût du gap

def aligne_custom(s1, s2, sim, gap):
    n1, n2 = len(s1), len(s2)
    sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]

    # Initialisation des bords avec le coût de gap
    for i in range(1, n1 + 1):
        sc[i][0] = i * gap # -1 est remplacé par gap
    for j in range(1, n2 + 1):
        sc[0][j] = j * gap # -1 est remplacé par gap

    # Le reste
    for i in range(1, n1 + 1):
        for j in range(1, n2 + 1):
            
            # 1. Score de Gap dans s2 (déplacement vertical)
            score_gap_s2 = gap + sc[i - 1][j]
            
            # 2. Score de Gap dans s1 (déplacement horizontal)
            score_gap_s1 = gap + sc[i][j - 1]
            
            # 3. Score d'alignement (déplacement diagonal)
            # Utilisation de la matrice sim
            score_sim = sim[s1[i - 1]][s2[j - 1]] + sc[i - 1][j - 1]
            
            # Score maximal parmi les trois options
            sc[i][j] = max(score_gap_s1, score_gap_s2, score_sim)
            
    return sc[n1][n2]

def chemins(n, m):
    """
    Calcule le nombre de chemins de (0, 0) à (n, m) sur une grille, 
    avec déplacements uniquement à droite ou en bas.
    """
    # La grille aura (n+1) lignes et (m+1) colonnes
    grille = [[0] * (m + 1) for _ in range(n + 1)]
    
    # Initialisation des bords (Cas de base: 1 chemin pour atteindre n'importe quelle case de la bordure)
    for i in range(n + 1):
        grille[i][0] = 1
    for j in range(m + 1):
        grille[0][j] = 1
        
    # Remplissage de la grille par approche ascendante
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # Le nombre de chemins pour (i, j) est la somme des chemins depuis le haut et la gauche
            grille[i][j] = grille[i - 1][j] + grille[i][j - 1]
            
    return grille[n][m]

# Vérification : chemins(2, 2) = 6 (Comme mentionné en introduction)