Les patterns de DP à connaître
AvancéPresque tous les problèmes de DP d'entretien sont une variante d'une poignée de formes.
| Pattern | État | Exemples classiques |
|---|---|---|
| 1D (suite) | dp[i] | Escaliers, voleur de maisons, monnaie |
| Grille 2D | dp[r][c] | Chemins uniques, somme minimale sur une grille |
| Sac à dos (knapsack) | dp[i][capacité] | Partition en deux sous-ensembles égaux, somme cible |
| Deux chaînes | dp[i][j] | Plus longue sous-séquence commune (LCS), distance d'édition |
| Intervalle | dp[gauche][droite] | Plus longue sous-chaîne palindrome, multiplication de matrices |
Exemple 2D : chemins dans une grille#
Nombre de chemins d'un coin à l'autre en n'allant que vers la droite ou le bas : dp[r][c] = dp[r-1][c] + dp[r][c-1]. On peut réduire la mémoire à une seule ligne, puisque chaque case ne dépend que de sa voisine du dessus et de celle de gauche.
function uniquePaths(rows: number, cols: number): number {
const dp = new Array<number>(cols).fill(1); // première ligne : un seul chemin
for (let r = 1; r < rows; r++) {
for (let c = 1; c < cols; c++) {
dp[c] += dp[c - 1]; // dessus (dp[c]) + gauche (dp[c-1])
}
}
return dp[cols - 1];
}
Cas pratique : face à « nombre de façons », « minimum/maximum avec des choix à chaque étape » ou « existe-t-il un sous-ensemble tel que… », pensez DP. Écrivez l'état et la transition sur papier avant de coder : 80 % du travail est là.