#Dp
12 articles avec ce tag.
Algorithmes & Structures de données
Burst Balloons
Des ballons portent des nombres. Éclater le ballon i rapporte nums[gauche] × nums[i] × nums[droite] (les voisins ACTUELS). Maximise le total. Ex : [3,1,5,8] → 167. Considéré comme l'un des DP les plus difficiles du catalogue.
Difficile
·
2 min
Algorithmes & Structures de données
Climbing Stairs
Tu montes un escalier de N marches. À chaque pas tu montes 1 ou 2 marches. Combien de façons distinctes d'atteindre le sommet ? Ex : N=3 → 3 façons (1+1+1, 1+2, 2+1).
Facile
·
2 min
Algorithmes & Structures de données
Coin Change
Avec des pièces de valeurs données (quantité illimitée), quel est le NOMBRE MINIMAL de pièces pour atteindre exactement un montant ? (-1 si impossible). Ex : coins=[1,2,5], amount=11 → 3 (5+5+1).
Moyen
·
2 min
Algorithmes & Structures de données
Edit Distance
Nombre MINIMAL d'opérations (insérer, supprimer, remplacer un caractère) pour transformer word1 en word2. Ex : "horse" → "ros" = 3. La distance de Levenshtein, au cœur des correcteurs orthographiques.
Difficile
·
2 min
Algorithmes & Structures de données
House Robber
Un voleur longe une rue de maisons contenant nums[i] euros, mais ne peut pas cambrioler deux maisons ADJACENTES. Quel butin maximal ?
Moyen
·
2 min
Algorithmes & Structures de données
House Robber II
Même problème, mais les maisons forment un CERCLE : la première et la dernière sont adjacentes. Butin maximal ?
Moyen
·
2 min
Algorithmes & Structures de données
Longest Common Subsequence
Longueur de la plus longue sous-suite commune à deux chaînes (mêmes caractères, même ordre, sauts autorisés). Ex : "abcde" et "ace" → 3. La base de git diff et des outils de comparaison.
Moyen
·
2 min
Algorithmes & Structures de données
Longest Increasing Subsequence
Trouve la longueur de la plus longue sous-suite STRICTEMENT croissante (pas forcément contiguë : on peut sauter des éléments en gardant l'ordre). Ex : [10,9,2,5,3,7,101,18] → 4 ([2,3,7,101]).
Moyen
·
2 min
Algorithmes & Structures de données
Longest Palindromic Substring
Trouve la plus longue sous-chaîne palindrome d'une chaîne. Ex : "babad" → "bab" (ou "aba").
Moyen
·
2 min
Algorithmes & Structures de données
Maximum Subarray (Kadane)
Trouve le sous-tableau CONTIGU dont la somme est maximale, et renvoie cette somme. Ex : [-2,1,-3,4,-1,2,1,-5,4] → 6 (le sous-tableau [4,-1,2,1]).
Moyen
·
2 min
Algorithmes & Structures de données
Regular Expression Matching
Implémente un matching de regex complet entre s et un pattern p supportant '.' (n'importe quel caractère) et '*' (zéro ou plusieurs occurrences du caractère PRÉCÉDENT). Le match doit couvrir toute la chaîne.
Difficile
·
3 min
Algorithmes & Structures de données
Word Break
Une chaîne s peut-elle être découpée en une suite de mots appartenant tous à un dictionnaire (mots réutilisables) ? Ex : s="leetcode", dict=["leet","code"] → vrai.
Moyen
·
2 min