メモ化を使った再帰による編集距離の導出を簡単にしたいです。

Question

長さがlen_x、len_yの二つの文字列の編集距離(レーベンシュタイン距離)を、二次元配列memo[len_x+1][len_y+1]に1度計算済みの編集距離を保存することで計算量をおさえつつ求めたいです。
同じ計算が必要になったときにこの保存してあった編集距離の値を参照する…というプログラムです。

最小で以下の再帰関数ldmemoの呼び出し回数をlen_x*len_yに抑えられることは分かっているのですが、実装の仕方が分かりません。

以下のメモ化の場合、例えば2文字と2文字の文字列の場合、再帰関数ldmemoの呼び出し回数は13回、3文字と3文字の場合28回、4文字と4文字の場合49回となります。これをそれぞれ22=4回、33=9回、4*4=16回…となるように実装したいです。

#include <stdio.h>
#include <stdlib.h>

int countm=0;  //再帰関数ldmemoの呼び出し回数

int ldmemo(char *X,int m,char *Y,int n,int **memo);

int main(void)
{
  char *data_x;
  char *data_y;
  int len_x,len_y;
  int **memo;
  //memo:(len_x+1)*(len_y+1)要素数の二次元配列(標準入力からの読み取りは省略しています)

  for(int i=0; i<len_x+1; ++i){  //memoを全て-1に初期化
    for(int j=0; j<len_y+1, ++j){
      memo[i][j]=-1;
    }
  }

  printf("%d ",ldmemo(data_x,len_x,data_y,len_y,memo));  //編集距離を出力
  printf("%d\n",countm);  //再帰関数の呼び出し回数を出力
}

int delta(char *X,int a,char *Y,int b)  //X[a]とY[b]の合否によって0or1を返す
{
  if(X[a]==Y[b]){
    return 0;
  }else{
    return 1;
  }
}

int ldmemo(char *X,int m,char *Y,int n,int **memo)  //改良したい再帰関数
{
  int edit=0; //返り値(編集距離)

  if(memo[m][n]!=-1){  //求める編集距離が既にメモされている場合それを採用
    edit_d=memo[m][n];
  }else if(m>=0 && n>=0){  //そうでない場合再帰によって編集距離edit_dを求めつつメモに記録
    if(m==0 || n==0){
      edit_d=vmax_(m,n);  //mとnの最大値を返す
      memo[m][n]=edit_d;
    }else{
      memo[m-1][n-1]=ldmemo(X,m-1,Y,n-1,memo);
      ++countm;

      memo[m-1][n]=ldmemo(X,m-1,Y,n,memo);
      ++countm;

      memo[m][n-1]=ldmemo(X,m,Y,n-1,memo);
      ++countm;

      edit_d=vmin3_(memo[m-1][n-1]+delta(X,m-1,Y,n-1),memo[m-1][n]+1,memo[m][n-1]+1);
      //vmin3_:3つの整数の最小値を返す
    }
  }
  memo[m][n]=edit_d;
  return edit_d;
}   

Answer 1

呼び出し回数をカウントする位置が悪いです
最初の呼び出しとメモ化した計算結果を返すだけの呼び出しとを区別せずカウントしてます
関数が呼び出されたとき、メモ化されておらず計算が必要な場合に1度だけカウントするように変えれば期待した動作になるでしょう。

Answer 2

計算量がO(MN)となることと、この問題においての再帰回数が最大MN回に収まることは等価ではありません。
レーベンシュタイン問題の計算量がO(MN)となるアルゴリズムは以下の記事を参照してください。
疑似コードに関して最も理解しやすいのはwikipediaの記事。
レーベンシュタイン距離 | wikipedia
一般式の考え化がわかりやすいのはこのqiitaの記事。
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～

2重ループの中身（本処理）の回数が高々MN回となるからO(MN)と表します。
上記の記事では再帰を使っていません。