SPOJ - Edit Distance Problem Solution - Famous DP problem

SPOJ - Edit Distance Problem Solution - Famous DP problem

Solution:-

#include<bits/stdc++.h>

using namespace std;

#define MAX 2010

int dp[MAX][MAX];

void init(int len)

{

    for(int i=0;i<=len;i++)

        dp[i][0]=dp[0][i]=i;

}

int min_val(int a,int b,int c)

{

    int p=INT_MAX;

    p=p>a?a:p;

    p=p>b?b:p;

    p=p>c?c:p;

    return p;

}

int main()

{

    int tc;

    int len1,len2;

    cin>>tc;

    while(tc--)

    {

        string a,b;

        cin>>a>>b;

        len1=a.length();

        len2=b.length();

        init(max(len1,len2));

        for(int i=1;i<=len1;i++)

            for(int j=1;j<=len2;j++)

            {

                if(a[i-1]==b[j-1])

                    dp[i][j]=dp[i-1][j-1];

                else

                    dp[i][j]=1+min_val(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]);

             }

        cout<<dp[len1][len2]<<endl;

    }

    return 0;

}