動的計画法Intermediate

最長共通部分列（LCS）

2つの列に同じ順序で存在する最長の部分列を見つけます。動的計画法を使用して解テーブルを構築します。DNA配列アライメント、ファイル差分ツール（diff）、盗作検出などの応用があります。

#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 動的計画法

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

フィボナッチ数列（動的計画法）

Beginner

動的計画法を使用して冗長な計算を避けながらフィボナッチ数を効率的に計算します。メモ化の力を示し、指数時間の再帰的解を線形時間アルゴリズムに変換します。動的計画法の概念への古典的な入門です。

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 動的計画法