Programmation dynamique : exemples, problèmes classiques et solutions optimisées

Les problèmes de programmation dynamique peuvent sembler intimidants lors d'un entretien technique. Même en sachant qu'une approche DP est nécessaire, trouver une solution efficace sous contrainte de temps est un défi majeur.

La clé pour exceller ? Pratiquer un maximum de problèmes. Pas besoin de mémoriser chaque solution, mais familiarisez-vous avec les patterns d'implémentation.

Qu'est-ce que la programmation dynamique ?

La programmation dynamique (DP) optimise les algorithmes récursifs en résolvant des problèmes d'optimisation informatique ou mathématique. Elle décompose un problème complexe en sous-problèmes plus simples, dont la solution optimale dépend des optima des sous-problèmes.

Elle s'applique aux solutions récursives avec sous-problèmes chevauchants et optimaux. L'idée : mémoriser les résultats (mémoïsation ou tabulation) pour éviter les recalculs.

Les algorithmes DP offrent une complexité polynomiale, passant souvent d'exponentielle à polynomiale, pour des exécutions bien plus rapides que la récursivité pure ou le backtracking.

Maintenant, explorons des problèmes classiques et leurs solutions expertes.

Problèmes classiques de programmation dynamique

1. Problème du sac à dos (0/1)

Énoncé

Donnés un ensemble d'objets avec poids et valeurs, sélectionnez un sous-ensemble maximisant la valeur totale sans dépasser la capacité W du sac. Version 0/1 : chaque objet pris ou non.

Tableaux : values[0..n-1] et weights[0..n-1].

Algorithme (tabulation)

• Créez un tableau 2D dp[n+1][W+1] : dp[i][w] = max valeur avec i premiers objets et capacité w.
• dp[i][w] = max( dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]] ) si weights[i-1] ≤ w, sinon dp[i-1][w].
• Base : dp[0][*] = 0 et dp[*][0] = 0.

Code Python

def knapsack(W, n, values, weights):
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

2. Problème du rendu de monnaie

Énoncé

Données des dénominations de pièces, trouvez le minimum de pièces pour un montant donné.

Algorithme

• Tableau dp[montant+1] : dp[i] = min pièces pour i.
• dp[0] = 0 ; init dp[1..montant] = infini.
• Pour chaque i de 1 à montant, pour chaque pièce k ≤ i : dp[i] = min(dp[i], dp[i-k] + 1).

Code Python

def coin_change(coins, montant):
    dp = [float('inf')] * (montant + 1)
    dp[0] = 0
    for i in range(1, montant + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[montant] if dp[montant] != float('inf') else -1

3. Suite de Fibonacci

Énoncé

Générez F(n) où F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).

Algorithme (bottom-up)

• Tableau dp[n+1] ; dp[0]=0, dp[1]=1.
• Pour i=2 à n : dp[i] = dp[i-1] + dp[i-2].

Code Python

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

4. Sous-séquence croissante la plus longue (LIS)

Énoncé

Trouvez la longueur de la LIS dans un tableau (éléments strictement croissants, non contigus).

Algorithme

• Tableau dp[n] : dp[i] = longueur LIS se terminant à i.
• dp[0]=1 ; pour i=1 à n-1 : dp[i]=1 + max(dp[j] pour j
• Max de dp.

Code Python

def length_of_lis(arr):
    n = len(arr)
    if n == 0:
        return 0
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Implémentez ces solutions

Avec ces exemples phares (sac à dos, monnaie, Fibonacci, LIS), implémentez-les dans votre IDE. Référez-vous aux algorithmes si besoin.

Maîtrisez la DP sur LeetCode ou HackerRank pour briller en entretien. Ouvrez votre IDE et codez !