3-5.c

#include <stdio.h>
#include <string.h>

int countLd=0;
int countMemo=0;
int memo[100][100]={};

int min3(int a, int b, int c)
{
  int temp;

  if(b>c)
    {
      temp=b;
      b=c;
      c=temp;
    }

  if(a>b)
    {
      temp=a;
      a=b;
      b=temp;
    }

  return a;
}

/* 3-2の関数 */
int ld(char *X, int m, char *Y, int n)
{
  int delta;

  countLd++;

  if(m==0 || n==0)
    {
      if(m>0)
        {
          return m;
        }
      else
        {
          return n;
        }
    }
  else
    {
      if(X[m-1]==Y[n-1])
        {
          delta=0;
        }
      else
        {
          delta=1;
        }

      return min3(ld(X, m-1, Y, n-1)+delta,
		  ld(X, m-1, Y, n)+1,
		  ld(X, m, Y, n-1)+1);
    }
}

/* メモ化の関数 */
int ldMemo(char *X, int m, char *Y, int n)
{
  int delta, a, b, c, ans;

  countMemo++;

  if(m==0 || n==0)
    {
      if(m>0)
        {
          return m;
        }
      else
        {
          return n;
        }
    }
  else
    {
      if(X[m-1]==Y[n-1])
        {
          delta=0;
        }
      else
        {
          delta=1;
        }


      if(memo[m-1][n-1]!=0)
        {
	  a=memo[m-1][n-1];
        }
      else
        {
	  a=ldMemo(X, m-1, Y, n-1);
	  memo[m-1][n-1]=a;
        }

      if(memo[m-1][n]!=0)
        {
	  b=memo[m-1][n];
        }
      else
        {
	  b=ldMemo(X, m-1, Y, n);
	  memo[m-1][n]=b;
        }

      if(memo[m][n-1]!=0)
        {
	  c=memo[m][n-1];
        }
      else
        {
	  c=ldMemo(X, m, Y, n-1);
	  memo[m][n-1]=c;
        }


      ans=min3(a+delta, b+1, c+1);

      return ans;
    }
}


int main()
{
  char X[100], Y[100];
  int  m, n, CLd, CMemo, s;

  while((s=getchar())!=EOF)
  {
      scanf("%s", X);
      scanf("%s", Y);

      m=strlen(X);
      n=strlen(Y);

      CLd=ld(X, m, Y, n);
      CMemo=ldMemo(X, m, Y, n);

      printf("%d\n", CMemo);
      fprintf(stderr, "%d,%d,%d,%d,%d\n", m, n, m*n, countLd, countMemo);
  }

  return 0;
}