from functools import lru_cache

# La PD s'applique quand un problème a : (1) sous-structure optimale, (2) sous-problèmes qui se chevauchent

# --- Fibonacci : de l'exponentiel au linéaire ---
def fib_naif(n: int) -> int:
    # O(2^n) : recalcule fib(3) des dizaines de fois pour n grand
    if n <= 1:
        return n
    return fib_naif(n - 1) + fib_naif(n - 2)

def fib_memoise(n: int, cache: dict | None = None) -> int:
    # Top-down (mémoïsation) : récursif, mais chaque sous-problème résolu UNE SEULE fois
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]           # O(1) : résultat déjà calculé
    if n <= 1:
        return n
    cache[n] = fib_memoise(n - 1, cache) + fib_memoise(n - 2, cache)
    return cache[n]
# O(n) temps, O(n) espace (cache + pile de récursion)

@lru_cache(maxsize=None)
def fib_lru(n: int) -> int:
    # Même idée, mémoïsation automatique fournie par la bibliothèque standard
    if n <= 1:
        return n
    return fib_lru(n - 1) + fib_lru(n - 2)

def fib_bottom_up(n: int) -> int:
    # Bottom-up (tabulation) : itératif, construit la solution du plus petit au plus grand sous-problème
    if n <= 1:
        return n
    table = [0] * (n + 1)
    table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

def fib_espace_optimise(n: int) -> int:
    # O(1) espace : on n'a besoin que des DEUX derniers résultats, pas de toute la table
    if n <= 1:
        return n
    precedent, courant = 0, 1
    for _ in range(2, n + 1):
        precedent, courant = courant, precedent + courant
    return courant

assert fib_naif(10) == fib_memoise(10) == fib_lru(10) == fib_bottom_up(10) == fib_espace_optimise(10) == 55

# --- Chemins dans une grille : illustration du passage récursif -> tabulation ---
def chemins_uniques_naif(m: int, n: int) -> int:
    # Nombre de chemins pour aller du coin (0,0) au coin (m-1,n-1) en ne se déplaçant qu'à droite/bas
    if m == 1 or n == 1:
        return 1
    return chemins_uniques_naif(m - 1, n) + chemins_uniques_naif(m, n - 1)   # O(2^(m+n)) -- très lent

def chemins_uniques_dp(m: int, n: int) -> int:
    # O(m*n) : table[i][j] = nombre de chemins pour atteindre la case (i, j)
    table = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            table[i][j] = table[i - 1][j] + table[i][j - 1]   # vient soit d'en haut, soit de la gauche
    return table[m - 1][n - 1]

assert chemins_uniques_dp(3, 7) == chemins_uniques_naif(3, 7) == 28

# --- Somme maximale d'un sous-tableau contigu (Kadane) : DP en O(n), O(1) espace ---
def sous_tableau_max(tableau: list[int]) -> int:
    max_courant = max_global = tableau[0]
    for x in tableau[1:]:
        # à chaque étape : soit on étend le sous-tableau précédent, soit on recommence à x
        max_courant = max(x, max_courant + x)
        max_global = max(max_global, max_courant)
    return max_global

assert sous_tableau_max([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6   # [4, -1, 2, 1]

# --- Nombre de façons de monter un escalier (variante de Fibonacci) ---
def compter_facons_escalier(n: int, pas_autorises: list[int] = [1, 2]) -> int:
    table = [0] * (n + 1)
    table[0] = 1   # une seule façon d'être déjà arrivé : ne rien faire
    for i in range(1, n + 1):
        for pas in pas_autorises:
            if i - pas >= 0:
                table[i] += table[i - pas]
    return table[n]

assert compter_facons_escalier(4) == 5   # (1,1,1,1)(1,1,2)(1,2,1)(2,1,1)(2,2)