動的計画法Intermediate

編集距離（レーベンシュタイン）

1つの文字列を別の文字列に変換するために必要な単一文字編集（挿入、削除、置換）の最小数を計算する動的計画法アルゴリズムです。スペルチェック、DNA配列アライメント、自然言語処理の基礎です。

#dynamic-programming#strings#levenshtein#spell-check

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

String 1 (Source)

String 2 (Target)

Example String Pairs:

How it works

• Minimum edits to transform string1 to string2
• Operations: insert, delete, replace
• Dynamic programming approach
• O(m × n) time and space complexity
• Also known as Levenshtein distance

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

行列連鎖乗算

Advanced

スカラー乗算の数を最小化するために行列の連鎖を括弧でくくる最適な方法を見つけます。CLRSの第15章の古典的な動的計画法の問題です。

O(n³)

O(n²)

dynamic-programmingoptimization

Start Learning

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

Beginner

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

O(n)

dynamic-programmingmemoization

Start Learning

最長共通部分列（LCS）

Intermediate

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

O(m × n)

dynamic-programmingstrings

Start Learning

Back to 動的計画法