La programmation dynamique est peut-être le fléau de l’existence de la plupart des ingénieurs logiciels. Je ne pense pas qu’il y ait un sujet sur lequel j’ai reçu plus de questions.
Et je le comprends totalement.
Les interviewers aiment poser ces questions parce qu’elles sont difficiles.
Les interviewés ont vraiment du mal parce qu’ils n’ont pas de cadre de résolution de problèmes pour aborder les problèmes de PD.
Cela signifie que chaque fois que vous essayez de résoudre un problème de programmation dynamique, vous repartez de la case départ. Vous ne pouvez pas appliquer les modèles que vous avez vus avec d’autres problèmes de DP parce qu’ils semblent totalement différents. Donc, vous recommencez toujours et essayez de résoudre ces problèmes difficiles à partir de zéro.
Dans ce post, je veux vous montrer une meilleure façon.
Les vidéos suivantes vous guideront à travers 6 des problèmes de DP les plus courants que vous pouvez vous attendre à voir dans vos entretiens. Si vous apprenez ces problèmes et apprenez à appliquer la méthode FAST, vous serez en très bonne position pour aborder la programmation dynamique dans vos entretiens.
Protip : Si vous êtes encore novice en programmation dynamique, consultez d’abord notre ebook gratuit de 42 pages, Programmation dynamique pour les entretiens
Voyez les problèmes :
Monnaie la plus petite
Donné un montant d’entrée de monnaie x, écrivez une fonction pour déterminer le nombre minimum de pièces de monnaie nécessaires pour faire ce montant de monnaie.
eg. (avec des pièces américaines)
|
1
2
3
4
|
. change(1) = 1
change(3) = 3
change(7) = 3
change(32) = 4
|
Longest Common Substring
Donné deux chaînes de caractères, écrivez une fonction qui renvoie la plus longue sous-chaîne commune.
eg.
longestSubstring("ABAB", "BABA") = "ABA"
Nombre de Fibonacci
Donné un entier n, écrivez une fonction qui calcule le nième nombre de Fibonacci.
eg.
fibonacci(1) = 1fibonacci(5) = 5fibonacci(10) = 55
Sous-matrice carrée
Donné un tableau 2D de 1s et 0s, trouvez le plus grand sous-matrice carré de tous les 1s.
eg.
|
1
2
3
|
subarray(
) = 2
|
Produit matriciel
Donné une matrice, trouver le chemin du haut à gauche au bas à droite avec le plus grand produit en se déplaçant uniquement vers le bas et la droite.
eg.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
1 -> 4 -> 7 -> 8 -> 9
2016
-1 -> 4 -> 5 -> -6 -> 9
1080
|
0-1 Sac à dos
Donné une liste d’éléments avec des valeurs et des poids, ainsi qu’un poids max, trouvez la valeur maximale que vous pouvez générer à partir d’éléments dont la somme des poids est inférieure au max.
eg.
|
1
2
3
|
items = {(w:1, v:6), (w:2, v:10), (w:3, v:12)}
poids max = 5
sac à dos (articles, poids max) = 22
|