DP sur LeetCode : 3 problèmes avec formules de récurrence

Programmation Dynamique : Une Approche Intuitive pour Trois Problèmes LeetCode

La programmation dynamique (DP) résout les problèmes de comptage et d'optimisation via des relations de récurrence. Examinons les problèmes 62 (Chemins Uniques), 64 (Somme Minimale du Chemin) et 70 (Monter les Escaliers). Chacun illustre les caractéristiques clés de la DP : sous-structure optimale et sous-problèmes qui se chevauchent.

Chemins Uniques : Compter les Itinéraires sur une Grille

Un robot se déplace sur une grille m × n de (0,0) à (m-1,n-1), en allant uniquement à droite ou vers le bas. Trouvez le nombre de chemins uniques.

Tout chemin consiste en (m-1) pas vers le bas et (n-1) pas vers la droite. Une solution combinatoire utilise le coefficient binomial C(m+n-2, m-1). Cependant, une approche algorithmique est attendue lors des entretiens.

Définissez dp[i][j] comme le nombre de chemins vers la cellule (i,j). Relation de récurrence :

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Conditions aux limites :

• dp[0][j] = 1 (première ligne)
• dp[i][0] = 1 (première colonne)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        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]

Complexité temporelle O(m·n). La solution utilise la règle d'addition pour des ensembles disjoints de chemins.

Somme Minimale du Chemin : Minimiser le Coût du Parcours

Étant donné une grille m × n avec des nombres non négatifs. Trouvez la somme minimale des valeurs sur un chemin de (0,0) à (m-1,n-1) en se déplaçant à droite ou vers le bas.

Un algorithme glouton (choisir le minimum local) échoue—il mène à des impasses avec des valeurs élevées. Une optimisation globale est nécessaire.

Définissez dp[i][j] comme le coût minimal pour atteindre (i,j). Relation de récurrence :

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Conditions aux limites :

dp[0][0] = grid[0][0]
for j in range(1, n): dp[0][j] = grid[0][j] + dp[0][j-1]
for i in range(1, m): dp[i][0] = grid[i][0] + dp[i-1][0]

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for j in range(1, n):
            dp[0][j] = grid[0][j] + dp[0][j - 1]
        for i in range(1, m):
            dp[i][0] = grid[i][0] + dp[i - 1][0]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

Complexité O(m·n). Chaque valeur est utilisée pour toutes les cellules suivantes.

Monter les Escaliers : Nombres de Fibonacci en DP

Monter des escaliers avec n marches (1 ≤ n ≤ 45), chaque pas est de 1 ou 2 marches. Trouvez le nombre de façons.

Pour n=1 : 1 façon

n=2 : 2 façons (1+1, 2)

n=3 : 3 façons (1+1+1, 1+2, 2+1)

Relation de récurrence :

dp[n] = dp[n-1] + dp[n-2]

Une récursion simple mène à une complexité exponentielle O(φ^n) due aux calculs répétés. Un tableau DP résout le problème :

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1], dp[2] = 1, 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

Une version optimisée utilise O(1) mémoire avec deux variables.

Signes des Problèmes de Programmation Dynamique

Appliquez la DP lorsque deux conditions sont remplies :

• Sous-structure optimale : la solution optimale est composée de solutions optimales aux sous-problèmes.
• Sous-problèmes qui se chevauchent : les mêmes sous-problèmes sont calculés plusieurs fois.

| Problème | Sous-structure Optimale | Sous-problèmes qui se Chevauchent |

|--------|-------------------------|---------------------------|

| Chemins Uniques | Somme des chemins des cellules adjacentes | Chaque chemin vers une cellule se chevauche |

| Somme Minimale du Chemin | Coût minimal des voisins | Le coût est utilisé pour toutes les cellules en dessous/à droite |

| Monter les Escaliers | Somme de n-1 et n-2 | Les appels récursifs se répètent |

Points Clés à Retenir

• Les relations de récurrence définissent l'essence de la DP : dp[i][j] dépend uniquement des valeurs adjacentes déjà calculées.
• Les conditions aux limites sont remplies séparément pour la première ligne/colonne ou les cas de base.
• La complexité temporelle est toujours O(taille de l'entrée) avec une implémentation tabulaire appropriée.
• La mémoire peut être optimisée : pour les grilles—une ligne, pour les problèmes linéaires—deux variables.
• La combinatoire offre souvent un raccourci mathématique, mais les solutions algorithmiques sont plus importantes pour les entretiens.

— Editorial Team