質問編集履歴
2
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -112,7 +112,7 @@
|
|
|
112
112
|
|
|
113
113
|
|
|
114
114
|
|
|
115
|
-
memo[m][n
|
|
115
|
+
memo[m-1][n]=ldmemo(X,m-1,Y,n,memo);
|
|
116
116
|
|
|
117
117
|
++countm;
|
|
118
118
|
|
1
追記
test
CHANGED
|
@@ -1 +1 @@
|
|
|
1
|
-
メモ化を使った再帰による編集距離の導出
|
|
1
|
+
メモ化を使った再帰による編集距離の導出を簡単にしたいです。
|
test
CHANGED
|
@@ -1,4 +1,6 @@
|
|
|
1
|
-
長さがlen_x、len_yの二つの文字列の編集距離(レーベンシュタイン距離)を、二次元配列memo[len_x+1][len_y+1]に計算済みの編集距離を
|
|
1
|
+
長さがlen_x、len_yの二つの文字列の編集距離(レーベンシュタイン距離)を、二次元配列memo[len_x+1][len_y+1]に1度計算済みの編集距離を保存することで計算量をおさえつつ求めたいです。
|
|
2
|
+
|
|
3
|
+
同じ計算が必要になったときにこの保存してあった編集距離の値を参照する…というプログラムです。
|
|
2
4
|
|
|
3
5
|
|
|
4
6
|
|
|
@@ -7,6 +9,8 @@
|
|
|
7
9
|
|
|
8
10
|
|
|
9
11
|
以下のメモ化の場合、例えば2文字と2文字の文字列の場合、再帰関数ldmemoの呼び出し回数は13回、3文字と3文字の場合28回、4文字と4文字の場合49回となります。これをそれぞれ2*2=4回、3*3=9回、4*4=16回…となるように実装したいです。
|
|
12
|
+
|
|
13
|
+
|
|
10
14
|
|
|
11
15
|
|
|
12
16
|
|