情報科学 › アルゴリズムとデータ構造 › 動的計画法

編集距離の漸化式

定理 7.3（「動的計画法」§7） ・ ✓公理まで証明済み

x=x1x2⋯xmx = x_1 x_2 \cdots x_m、y=y1y2⋯yny = y_1 y_2 \cdots y_n を有限アルファベット上の文字列とし、0≤i≤m0 \le i \le m、0≤j≤n0 \le j \le n に対して D(i,j)=d(x1⋯xi, y1⋯yj)D(i,j) = d(x_1 \cdots x_i,\ y_1 \cdots y_j) とおく（i=0i = 0 や j=0j = 0 のときは空文字列とする）。このとき

D(i,0)=i(0≤i≤m),D(0,j)=j(0≤j≤n)D(i, 0) = i \quad (0 \le i \le m), \qquad D(0, j) = j \quad (0 \le j \le n)

であり、1≤i≤m1 \le i \le m、1≤j≤n1 \le j \le n に対して

D(i,j)=min⁡{ D(i−1,j)+1,  D(i,j−1)+1,  D(i−1,j−1)+[ xi≠yj ] }D(i,j) = \min\bigl\{\, D(i-1, j) + 1,\ \ D(i, j-1) + 1,\ \ D(i-1,j-1) + [\, x_i \ne y_j \,] \,\bigr\}

が成り立つ。ここで [ xi≠yj ][\,x_i \ne y_j\,] は xi≠yjx_i \ne y_j のとき 11、xi=yjx_i = y_j のとき 00 を表す。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を 前提 としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 0 件、定義なども含めて 1 件）。

印の意味: ✓公理まで証明済み ・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は 閉包の状況。

前提をたどる 証明が使う定理・定義（直接 1 件）

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

これを使っている定理

証明で明示的に参照している定理は、まだありません。

関連するノック 1 問