質問: 2つの文字列の編集距離を求めるプログラムです。 メモ化を一切せずに再帰を使って編集距離を求めたのですが、計算の重複を避けるために二次元配列memoを導入して同じプログラムを作りたい場合、 編集距離を求める時に 1配列memoに既に記録している場合、それを編集距離とみなす。 2配列memoに記録していない場合、再帰を利用して編集距離を求め、memoに格納する。 のいずれかを実行したいです。既に2は以下の通り完成しているので、1の「配列memo[m][n]に既に求めたい値が存在している場合、それを編集距離とする」をプラスして実装する際どうすればいいかを教えて頂きたいです。 vmax,vminはそれぞれ引数の最大値、最小値、deltaはX[a]==Y[b]の時0、X[a]!=Y[b]の時1を返り値とする関数です。 必要であれば以下のプログラムを変更することも構いません。 よろしくお願いいたします。 ``` int ldmemo(char *X,int m,char *Y,int n){ if( ??? ){ ??? //1の条件を挿入 }else if(m>=0 && n>=0){ if(m==0 || n==0){ edit_d=vmax_(m,n); memo[m][n]=edit_d; }else{ candi_edit_d[0]=ldmemo(X,m-1,Y,n-1)+delta(X,m-1,Y,n-1); candi_edit_d[1]=ldmemo(X,m-1,Y,n)+1; candi_edit_d[2]=ldmemo(X,m,Y,n-1)+1; edit_d=vmin3_(candi_edit_d[0],candi_edit_d[1],candi_edit_d[2]); memo[m][n]=edit_d; } } return edit_d; } ``` [追記] 問題のURLです。 http://ecei-tohoku.github.io/ppa/kadai3_19268ef8e7e3d19af4abf721821b2baef83ae0e0a69cf66263d8263fcf2c3418cegw/p32.html
回答: 最初に`memo[m][n]`を全部`-1`で埋めておくとかすれば、`-1`でなければ計算した結果であるというのがわかります