0Pricing
DSA Interview Prep · Leçon

DP ascendante avec tabulation

Convertissez les solutions descendantes en tableaux de DP itératifs et réduisez l’espace de O(n) à O(1) lorsque seules les dernières entrées sont nécessaires.

DP ascendante avec tabulation est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.

DP ascendante : l'approche par tabulation

La DP ascendante (tabulation) remplit un tableau contenant les réponses aux sous-problèmes, en commençant par les plus petits et en progressant jusqu'à la réponse. Au lieu de descendre par récursion et de mémoriser les résultats en remontant, vous effectuez les calculs de manière itérative, des cas de base vers la solution. Le tableau est généralement un tableau 1D ou 2D dont chaque case est calculée à partir de cases déjà remplies. Cela élimine complètement la récursion : pas de pile d'appels, pas de limite de récursion et une meilleure localité du cache.

# Converting top-down to bottom-up:
# Top-down: start at fib(n), recurse to smaller, cache
# Bottom-up: start at fib(0), fill table to fib(n)

# Key question for bottom-up:
# 'In what order do I fill the table so that when I compute dp[i],
# all values dp[i] depends on are already filled?'
# For Fibonacci: dp[i] needs dp[i-1] and dp[i-2]
# Fill order: i = 2, 3, 4, ..., n (left to right)
print('Bottom-up: fill small sub-problems first, build to answer')

Fibonacci ascendant

La version ascendante de Fibonacci remplit dp[0..n] de gauche à droite. dp[i] = dp[i-1] + dp[i-2] pour i >= 2. Les cas de base sont dp[0] = 0 et dp[1] = 1, stockés directement dans le tableau. Le temps d'exécution est de O(n) et l'espace mémoire de O(n) pour le tableau complet. Une fois que vous constatez que dp[i] ne dépend que des deux dernières valeurs, vous pouvez réduire l'espace mémoire à O(1) avec deux variables : c'est l'étape d'optimisation de l'espace mémoire.

def fib_bottom_up(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0] = 0  # base case
    dp[1] = 1  # base case
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print([fib_bottom_up(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

# Space-optimised to O(1):
def fib_optimised(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fib_optimised(50))  # 12586269025

Rendu de monnaie ascendant

Pour le rendu de monnaie, le tableau ascendant est dp[0..amount], où dp[i] = nombre minimal de pièces pour obtenir le montant i. Initialisez dp[0] = 0 (zéro pièce pour un montant nul) et dp[1..amount] = infini. Pour chaque montant i de 1 à la cible, essayez chaque pièce : si i >= coin, alors dp[i] = min(dp[i], 1 + dp[i - coin]). La réponse est dp[amount], ou -1 si sa valeur est encore infinie.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # base case: 0 coins for amount 0
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:  # can use this coin
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 5, 6, 9], 11))  # 2: (5+6)
print(coin_change([2], 3))             # -1: impossible
print(coin_change([1, 2, 5], 11))      # 3: 5+5+1
print(coin_change([186, 419, 83, 408], 6249))  # 20

Ordre de remplissage : l'idée essentielle

L'ordre de remplissage est au cœur de la DP ascendante. Pour tout état dp[i], tous les états dont il dépend doivent être calculés auparavant. Pour une DP 1D où dp[i] dépend de dp[i-1] et dp[i-2], remplissez le tableau de gauche à droite. Pour une DP 2D où dp[i][j] dépend de dp[i-1][j] et dp[i][j-1], remplissez-le ligne par ligne (de haut en bas, puis de gauche à droite). Dessinez toujours les flèches de dépendance avant de coder afin de confirmer l'ordre de remplissage.

# Fill order examples:

# 1D: dp[i] = f(dp[i-1], dp[i-2])
# Arrows point LEFT: fill LEFT TO RIGHT
# i: 0 -> 1 -> 2 -> ... -> n

# 2D: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# Arrows point LEFT and UP: fill TOP-LEFT TO BOTTOM-RIGHT
# Fill row 0 first, then row 1, etc.

# 2D reversed: dp[i][j] = f(dp[i+1][j], dp[i][j+1])
# Arrows point RIGHT and DOWN: fill BOTTOM-RIGHT TO TOP-LEFT
# Used in interval DP and some string problems

print('Draw dependencies first, then determine fill order')

LCS ascendante : tableau 2D

Le tableau ascendant de la plus longue sous-séquence commune est de dimensions (m+1) × (n+1), où dp[i][j] = LCS de s1[:i] et s2[:j]. Cas de base : dp[0][j] = dp[i][0] = 0 (une chaîne vide a une LCS de longueur 0 avec n'importe quelle chaîne). Remplissez le tableau ligne par ligne : si s1[i-1] == s2[j-1], dp[i][j] = 1 + dp[i-1][j-1] ; sinon dp[i][j] = max(dp[i-1][j], dp[i][j-1]). La réponse est dp[m][n].

def lcs_bottom_up(s1, s2):
    m, n = len(s1), len(s2)
    # (m+1) x (n+1) table, initialised to 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:         # characters match
                dp[i][j] = 1 + dp[i-1][j-1]
            else:                            # skip one character
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

print(lcs_bottom_up('abcde', 'ace'))   # 3
print(lcs_bottom_up('ABCBDAB', 'BDCAB'))  # 4: 'BCAB' or 'BDAB'

Optimisation de l'espace mémoire : tableau glissant

De nombreux tableaux DP 2D peuvent être réduits à 1D (ou à 2 lignes) en constatant que dp[i][j] ne dépend que de la ligne courante et de la ligne précédente. Conservez deux tableaux : prev et curr, ou mettez à jour un seul tableau dans le bon ordre. Pour la LCS, dp[i][j] dépend de dp[i-1][j], dp[i][j-1] et dp[i-1][j-1] : conserver uniquement la ligne précédente suffit.

def lcs_space_optimised(s1, s2):
    m, n = len(s1), len(s2)
    # Keep only one row (previous row state)
    prev = [0] * (n + 1)
    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = 1 + prev[j-1]  # dp[i-1][j-1]
            else:
                curr[j] = max(prev[j], curr[j-1])  # dp[i-1][j] and dp[i][j-1]
        prev = curr
    return prev[n]

print(lcs_space_optimised('abcde', 'ace'))   # 3
# Space: O(n) instead of O(mn)

Cambriolage de maisons ascendant

La version ascendante du cambriolage de maisons remplit dp[0..n-1], où dp[i] = gain maximal en cambriolant les maisons 0 à i. dp[0] = nums[0], dp[1] = max(nums[0], nums[1]) et, pour i >= 2 : dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Puisque dp[i] ne dépend que des deux dernières valeurs, l'espace mémoire peut immédiatement être optimisé à O(1) avec deux variables — un schéma courant pour une DP 1D ayant des dépendances à deux étapes.

def rob_bottom_up(nums):
    if not nums: return 0
    if len(nums) == 1: return nums[0]

    # Full table version: O(n) space
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    return dp[-1]

def rob_optimised(nums):
    # O(1) space: only need last two values
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
    return prev1

print(rob_optimised([2, 7, 9, 3, 1]))  # 12

Somme minimale d'un chemin dans une grille

Somme minimale d'un chemin (LeetCode #64) : trouvez un chemin du coin supérieur gauche au coin inférieur droit qui minimise la somme des valeurs (vous pouvez uniquement vous déplacer vers la droite ou vers le bas). DP 2D : dp[i][j] = somme minimale pour atteindre la case (i,j). dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Remplissez le tableau de gauche à droite et de haut en bas. Cas de base : dp[0][0] = grid[0][0] ; la première ligne se remplit uniquement vers la droite et la première colonne uniquement vers le bas.

def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
    # Fill first row (can only come from left)
    for c in range(1, cols):
        dp[0][c] = dp[0][c-1] + grid[0][c]
    # Fill first column (can only come from above)
    for r in range(1, rows):
        dp[r][0] = dp[r-1][0] + grid[r][0]
    # Fill rest of the table
    for r in range(1, rows):
        for c in range(1, cols):
            dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])
    return dp[rows-1][cols-1]

grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid))  # 7: 1+3+1+1+1

Modifier le tableau DP sur place

Lorsque l'espace supplémentaire est interdit, vous pouvez parfois modifier la grille d'entrée elle-même pour l'utiliser comme tableau DP. Pour la somme minimale d'un chemin, remplacez grid[i][j] par le coût minimal pour atteindre cette case. Cette méthode utilise O(1) espace supplémentaire, mais détruit l'entrée — mentionnez toujours ce compromis à la personne qui vous interroge et vérifiez qu'il est acceptable. Si l'entrée doit être conservée, utilisez plutôt l'approche du tableau glissant.

def min_path_sum_inplace(grid):
    rows, cols = len(grid), len(grid[0])
    # Modify grid in-place (O(1) extra space, destroys input)
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                continue  # starting cell
            elif r == 0:
                grid[r][c] += grid[r][c-1]  # first row
            elif c == 0:
                grid[r][c] += grid[r-1][c]  # first column
            else:
                grid[r][c] += min(grid[r-1][c], grid[r][c-1])
    return grid[rows-1][cols-1]

import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid)))  # 7

Comparaison des approches descendante et ascendante pour le rendu de monnaie

Les deux approches résolvent le problème du rendu de monnaie de manière optimale, mais diffèrent en pratique. L'approche descendante est plus simple à écrire et ne calcule que les sous-problèmes réellement accessibles. L'approche ascendante calcule tous les montants de 0 jusqu'à la cible, même ceux qui sont inaccessibles avec les pièces données et qui restent donc à l'infini. Pour les problèmes peu denses, avec peu d'états accessibles, l'approche descendante est plus efficace ; pour les problèmes denses, l'approche ascendante présente une surcharge moindre.

import functools

# Top-down: only computes reachable amounts
def coin_change_top(coins, amount):
    @functools.lru_cache(maxsize=None)
    def dp(rem):
        if rem == 0: return 0
        if rem < 0: return float('inf')
        return 1 + min(dp(rem - c) for c in coins)
    r = dp(amount)
    return r if r != float('inf') else -1

# Bottom-up: computes all amounts 0 to target
def coin_change_bottom(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if i >= c: dp[i] = min(dp[i], 1 + dp[i-c])
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change_top([1,5,6,9], 11))    # 2
print(coin_change_bottom([1,5,6,9], 11)) # 2

Chemins uniques : DP 2D classique

Chemins uniques (LeetCode #62) compte le nombre de chemins entre le coin supérieur gauche et le coin inférieur droit d'une grille m×n, en se déplaçant uniquement vers la droite ou vers le bas. La récurrence est simple : dp[i][j] = dp[i-1][j] + dp[i][j-1] — les chemins venant du dessus plus ceux venant de la gauche. Cas de base : la première ligne et la première colonne entières possèdent chacune exactement 1 chemin, puisqu'une seule direction est possible. Cette DP 2D se remplit en O(mn) time et peut être réduite à un espace O(n) grâce à une ligne glissante.

def unique_paths(m, n):
    # dp[i][j] = number of paths to reach cell (i,j)
    dp = [[1] * n for _ in range(m)]
    # Base: first row and first column are all 1
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

print(unique_paths(3, 7))   # 28
print(unique_paths(3, 2))   # 3

# O(n) space rolling row:
def unique_paths_opt(m, n):
    row = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j-1]
    return row[n-1]

print(unique_paths_opt(3, 7))  # 28

Vérification rapide

Évaluez votre compréhension des concepts de Structures de données et algorithmes — Préparation aux entretiens de programmation abordés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris : la DP ascendante avec tabulation et la manière de déterminer l'ordre de remplissage à partir des flèches de dépendance, l'optimisation de l'espace à l'aide de tableaux glissants (de O(mn) à O(n)) et du suivi de deux variables (de O(n) à O(1)), ainsi que les implémentations ascendantes de Fibonacci, du rendu de monnaie, de LCS, du problème du voleur de maisons et de la somme minimale d'un chemin. Ensuite, nous résoudrons de bout en bout les problèmes du rendu de monnaie et de l'escalier à coût minimal.

Questions Fréquemment Posées

La leçon « DP ascendante avec tabulation » est-elle gratuite ?

Oui — le texte complet de « DP ascendante avec tabulation » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « DP ascendante avec tabulation » ?

Convertissez les solutions descendantes en tableaux de DP itératifs et réduisez l’espace de O(n) à O(1) lorsque seules les dernières entrées sont nécessaires. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?

Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.

Combien de temps prend la leçon « DP ascendante avec tabulation » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?

Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Reconnaître la DP : sous-problèmes qui se recouvrent
  2. DP descendante avec mémoïsation
  3. DP ascendante avec tabulation
  4. Rendu de monnaie et escalier au coût minimal
← Retour à DSA Interview Prep