Reconnaître la DP : sous-problèmes qui se recouvrent

La programmation dynamique (DP) résout les problèmes complexes en les décomposant en sous-problèmes plus simples qui se chevauchent, en résolvant chaque sous-problème une seule fois et en stockant le résultat pour éviter les calculs redondants. La DP s'applique lorsqu'un problème possède deux éléments : des sous-problèmes qui se chevauchent (le même sous-problème est résolu plusieurs fois dans une récursion naïve) et une sous-structure optimale (la solution optimale peut être construite à partir des solutions optimales des sous-problèmes). Sans ces deux éléments, la DP n'est d'aucune utilité.

La suite de Fibonacci (fib(n) = fib(n-1) + fib(n-2)) est l'exemple classique des sous-problèmes qui se chevauchent. La récursion naïve a une complexité temporelle exponentielle O(2^n), car elle recalcule plusieurs fois les mêmes valeurs. L'arbre de récursion pour fib(6) montre que fib(3) est calculé 3 fois, que fib(2) l'est 5 fois, et ainsi de suite. Cette explosion exponentielle est exactement ce que la DP élimine en stockant les résultats déjà calculés.

Représenter l'arbre de récursion pour fib(5) révèle le gaspillage : chaque nœud engendre deux enfants, et des sous-arbres identiques apparaissent plusieurs fois. Le nombre total de nœuds de l'arbre est O(2^n). Lorsque vous observez ce schéma — des appels de fonction identiques avec les mêmes arguments qui se répètent dans l'arbre — cela indique que la DP peut être utile en mettant les résultats en cache. Cette capacité de visualisation est essentielle : si vous pouvez repérer les sous-arbres répétés, vous savez que la DP est applicable.

Pour reconnaître les sous-problèmes qui se chevauchent, écrivez la récursion par force brute, puis demandez-vous : « Y a-t-il plusieurs appels récursifs avec les mêmes (SAME) arguments ? » Si oui, la DP peut être utile. Parmi les formulations courantes dans les énoncés, on trouve : « nombre minimal/maximal de X », « combien de façons de faire Y », « pouvons-nous atteindre Z ? ». Ces formulations indiquent presque toujours un problème de sous-structure optimale, où la réponse à la position i dépend des réponses aux positions précédentes.

La sous-structure optimale signifie que la solution optimale d'un problème peut être construite à partir des solutions optimales de ses sous-problèmes. Par exemple, le plus court chemin de A à C passant par B est optimal si et seulement si les sous-chemins A→B et B→C sont chacun individuellement optimaux. Si cette propriété est vérifiée, vous pouvez construire l'optimum global de bas en haut à partir d'optima locaux. Les problèmes dépourvus de sous-structure optimale (par exemple, le plus long chemin dans un graphe général avec des cycles) ne peuvent pas être résolus avec la DP.

Monter des marches (LeetCode n° 70) : combien de façons distinctes pouvez-vous monter n marches en avançant d'une ou de deux marches à la fois ? Soit dp[i] le nombre de façons d'atteindre la marche i. Vous pouvez atteindre la marche i depuis la marche i-1 (un pas) ou depuis la marche i-2 (deux pas), donc dp[i] = dp[i-1] + dp[i-2]. C'est la suite de Fibonacci ! Cas de base : dp[1] = 1 et dp[2] = 2. Reconnaître que « monter des marches » se réduit à Fibonacci est une idée classique des entretiens.

Un cadre DP fiable en 3 étapes : 1. Définissez l'état — que représente dp[i] (ou dp[i][j]) ? Écrivez-le en anglais. 2. Écrivez la récurrence — exprimez dp[i] en fonction de sous-problèmes plus petits. Incluez tous les cas. 3. Déterminez l'ordre de remplissage — assurez-vous que dp[i-1] (et les autres dépendances) sont calculés avant dp[i]. Les cas de base initialisent la frontière. Ce cadre transforme une intuition DP floue en un plan d'implémentation concret.

La DP n'est pas toujours la solution. Utilisez une approche gloutonne lorsqu'un choix localement optimal mène toujours à la solution globalement optimale (sélection d'activités, jeu de sauts I). Utilisez diviser pour régner lorsque les sous-problèmes ne se chevauchent pas (tri fusion, recherche binaire). Utilisez BFS lorsque le problème consiste à trouver le plus court chemin dans un graphe non pondéré. La DP est correcte, mais souvent disproportionnée lorsqu'une approche gloutonne ou plus simple existe. Lors des entretiens, expliquez pourquoi vous avez choisi la DP plutôt que les autres approches.

Le nombre de sous-problèmes distincts détermine la complexité en temps et en espace mémoire de la DP. Pour une DP 1D sur une entrée de taille n, il y a O(n) sous-problèmes. Pour une DP 2D sur deux entrées de tailles m et n, il y a O(mn) sous-problèmes. Chaque sous-problème est résolu en O(k) temps (pour k choix à chaque étape), ce qui donne un temps total de O(n*k) ou O(mn*k). Comptez toujours d'abord les sous-problèmes distincts : cela vous donne la complexité temporelle de la DP avant même de l'implémenter.

Cambriolage de maisons (LeetCode #198) consiste à trouver le montant maximal que vous pouvez voler dans une rangée de maisons sans voler deux maisons adjacentes. Pour chaque maison, vous avez le choix : la voler (ajouter sa valeur et ignorer la précédente) ou l'ignorer (prendre le meilleur résultat précédent). dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Ce schéma de choix à chaque étape est la relation de récurrence de DP 1D la plus simple et apparaît dans des dizaines de problèmes d'entretien.

Vérifiez toujours votre DP par rapport à une solution par force brute sur de petites entrées. La force brute constitue votre référence de vérité. Une fois que la DP correspond à la force brute pour tous les cas d'essai, vous savez que la relation de récurrence est correcte. Ce n'est qu'alors que vous optimiserez l'espace mémoire. Cette approche pilotée par les essais — force brute → DP descendante → DP ascendante → DP optimisée en espace mémoire — est la méthode professionnelle pour développer et vérifier des solutions DP pendant un entretien.

Vérifiez votre compréhension des concepts de structures de données et d'algorithmes — préparation aux entretiens de programmation — présentés dans cette leçon.

Dans cette leçon, vous avez appris : les deux ingrédients de la DP (les sous-problèmes qui se chevauchent et la sous-structure optimale), comment visualiser l'arbre de récursion pour repérer les appels répétés, le cadre DP en trois étapes (définition de l'état, récurrence, ordre de remplissage), ainsi que les premiers exemples, notamment Fibonacci, les escaliers et le cambriolage de maisons. Ensuite, nous implémenterons la DP descendante avec mémoïsation.