Programmation dynamiqueIntermediate

Plus longue sous-séquence commune (LCS)

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.

#dynamic-programming#strings#sequences#optimization

Complexity Analysis

Time (Average)

O(m × n)

Expected case performance

Space

O(m × n)

Memory requirements

Time (Best)

O(m × n)

Best case performance

Time (Worst)

O(m × n)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 15•Section 15.4

Quick Presets

Text 1 (max 10 characters, letters only)Text 2 (max 10 characters, letters only)

LCS finds the longest subsequence common to both strings

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in Programmation dynamique

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

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

Back to Programmation dynamique