Programmation dynamique

Résolvez des problèmes d'optimisation complexes en les décomposant en sous-problèmes plus simples se chevauchant. Maîtrisez les approches de mémoïsation et ascendantes à travers des problèmes classiques comme les suites de Fibonacci, la plus longue sous-séquence commune, les problèmes du sac à dos et la multiplication en chaîne de matrices. Apprenez comment la programmation dynamique transforme des solutions en temps exponentiel en algorithmes en temps polynomial.

9 algorithmes

Matrix Chain Multiplication

Advanced

Finds the optimal way to parenthesize a chain of matrices to minimize the number of scalar multiplications. Classic dynamic programming problem from CLRS Chapter 15.

O(n³)

O(n²)

dynamic-programmingoptimization

Start Learning

Fibonacci (Programmation dynamique)

Beginner

Calcule efficacement les nombres de Fibonacci en utilisant la programmation dynamique pour éviter les calculs redondants. Démontre la puissance de la mémoïsation pour transformer une solution récursive en temps exponentiel en un algorithme en temps linéaire. Une introduction classique aux concepts de programmation dynamique.

O(n)

dynamic-programmingmemoization

Start Learning

Plus longue sous-séquence commune (LCS)

Intermediate

Trouve la plus longue sous-séquence présente dans deux séquences dans le même ordre. Utilise la programmation dynamique pour construire une table de solution. Les applications incluent l'alignement de séquences ADN, les outils de différence de fichiers (diff) et la détection de plagiat.

O(m × n)

dynamic-programmingstrings

Start Learning

Edit Distance (Levenshtein)

Intermediate

Dynamic programming algorithm that calculates the minimum number of single-character edits (insertions, deletions, substitutions) required to transform one string into another. Fundamental in spell checking, DNA sequence alignment, and natural language processing.

O(m × n)

dynamic-programmingstrings

Start Learning

0/1 Knapsack Problem

Intermediate

Classic dynamic programming problem where you must select items with given weights and values to maximize total value while staying within a weight capacity. Each item can only be taken once (0/1). Applications include resource allocation, portfolio optimization, and cargo loading.

O(n × W)

dynamic-programmingoptimization

Start Learning

Longest Increasing Subsequence

Intermediate

Find the longest subsequence where all elements are in increasing order. Classic DP problem.

O(n log n)

O(n)

dynamic-programmingbinary-search

Start Learning

Kadane's Algorithm (Maximum Subarray)

Intermediate

Elegant dynamic programming algorithm that finds the contiguous subarray with maximum sum in O(n) time. Combines greedy and DP principles by deciding at each step whether to extend the current subarray or start a new one. Essential for stock profit optimization, signal processing, and understanding DP optimization techniques.

O(n)

O(1)

dynamic-programminggreedy

Start Learning

Coin Change Problem

Intermediate

Classic dynamic programming problem that finds the minimum number of coins needed to make a target amount. Demonstrates optimal substructure where the solution depends on solutions to smaller amounts. Widely applied in financial systems, vending machines, and resource allocation optimization.

O(amount × coins)

O(amount)

dynamic-programmingoptimization

Start Learning

Palindrome Partitioning

Advanced

Dynamic programming problem that finds the minimum number of cuts needed to partition a string into palindromic substrings. Uses DP to precompute which substrings are palindromes, then finds optimal cuts. Applications include text segmentation, DNA sequence analysis, and string optimization problems.

O(n²)

dynamic-programmingstrings

Start Learning

💡 Conseil d'apprentissage

Commencez par les algorithmes de niveau débutant pour construire vos bases, puis progressez vers les sujets intermédiaires et avancés. Chaque algorithme comprend des visualisations interactives, une analyse de complexité et des exemples de code dans plusieurs langages.