文字列アルゴリズム:最長共通サブシーケンス、最短編集距離など

最長共通サブシーケンス、最短編集距離など文字列に関するアルゴリズムをゆっくり書きますが、実は配列に関するアルゴリズムです...
一、最長共通サブシーケンス
Solve 1のプッシュ式は次のとおりです.
dp[i][j] = 0                                         if i = 0 or j  = 0
dp[i][j] = dp[i-1][j-1]+1                       if s1[i-1] = s2[j-1]
dp[i][j] = max{dp[i-1][j],dp[i][j-1]}       if s1[i-1] != s2[j-1]
ここでi,jはs 1,s 2の文字の下付きではなくs 1の前のi文字とs 2の前のj文字であり、dp[i][j]はs 1の前のi文字とs 2の前のj文字の最も長い共通サブシーケンスを表す
Solve 1は最長共通サブシーケンスの1つのみを印刷し、同じ最長共通サブシーケンスを複数考慮しない
Solve 2は、数式を少し変換しました.
dp[i][j]はs 1前i+1文字とs 2前j+1文字の最長共通サブシーケンスを表し、あまり変換されていない
Solve 3は1次元配列のみでスペースの複雑さを低減
Solve 4は再帰的な書き方です

#include 
#include 
#include 
//#define _DEBUG
int max(int a, int b){
    return a>b?a:b;
}

void Solve1(char s1[], char s2[]){
    int i,j;//i、j     s1、s2  
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int dp[len1+1][len2+1];

    for(i = 0; i <= len1; ++i) dp[i][0] = 0;
    for(j = 0; j <= len2; ++j) dp[0][j] = 0;
    for(i = 1; i <= len1; ++i){
        for(j = 1; j <= len2; ++j){
            if(s1[i-1] == s2[j-1]){// i-1   j-1
                dp[i][j] = dp[i-1][j-1] + 1;
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    #ifdef _DEBUG
    for(i = 0; i <= len1; ++i){
        for(j = 0; j<= len2; ++j){
            printf("%d ",dp[i][j]);
        }
        printf("
");
    }
    #endif// _DEBUG
    printf("Solve1:%d
",dp[len1][len2]);

    for(i = len1; i >= 0; ){
        for(j = len2; j >= 0; ){
            if(s1[i-1] == s2[j-1]){
                printf("%c ",s1[i-1]);
                --i;
                --j;
            }else{
                if(dp[i][j-1] > dp[i-1][j]){
                    --j;
                }else{
                    --i;
                }
            }
        }
    }
    printf("
");
}

/*  
//dp[][0] dp[0][]  
void Solve2(char s1[], char s2[]){
    int i,j;
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int dp[len1][len2];

    for(i = 0; i < len1; ++i) dp[i][0] = s1[i]==s2[0]?1:0;
    for(j = 0; j < len2; ++j) dp[0][j] = s1[0]==s2[j]?1:0;
    for(i = 1; i < len1; ++i){
        for(j = 1; j < len2; ++j){
            if(s1[i] == s2[j]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }

    for(i = 0; i < len1; ++i){
        for(j = 0; j< len2; ++j){
            printf("%d ",dp[i][j]);
        }
        printf("
");
    }
    printf("%d
",dp[len1-1][len2-1]);
}
*/

void Solve2(char s1[], char s2[]){
    int i,j;//i、j s1 s2  
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int dp[len1][len2];
    int dp1 = 0;
    int dp2 = 0;
    dp[0][0] = s1[0]==s2[0]?1:0;
    for(i = 1; i < len1; ++i){
        if(dp1 == 0 && s1[i] == s2[0]) dp1 = 1;
        dp[i][0] = dp1;
    }
    for(j = 1; j < len2; ++j){
        if(dp2 == 0 && s1[0] == s2[j]) dp2 = 1;
        dp[0][j] = dp2;
    }

    for(i = 1; i < len1; ++i){
        for(j = 1; j < len2; ++j){
            if(s1[i] == s2[j]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    #ifdef _DEBUG
    for(i = 0; i < len1; ++i){
        for(j = 0; j< len2; ++j){
            printf("%d ",dp[i][j]);
        }
        printf("
");
    }
    #endif // _DEBUG
    printf("Solve2:%d
",dp[len1-1][len2-1]);
}

void Solve3(char s1[], char s2[]){
    int i,j;
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int dp[len2+1];

    for(j = 0; j <= len2; ++j){
        dp[j] = 0;
    }

    for(i = 1; i <= len1; ++i){
        for(j = 1; j <= len2; ++j){
            if(s1[i-1] == s2[j-1]){
                dp[j] = dp[j-1] + 1;
            }else{
                dp[j] = max(dp[j],dp[j-1]);
            }
        }
    }
    #ifdef _DEBUG
    for(j = 0; j<= len2; ++j) printf("%d ",dp[j]);
    printf("
");
    #endif // _DEBUG
    printf("Solve3:%d
",dp[len2]);
}

int Solve4(char s1[], char s2[], int i, int j,int dp[][20]){
    //    
    if(i==0 || j==0){
        dp[i][j] = 0;
        return dp[i][j];
    }
    if(dp[i][j] != -1){
        return dp[i][j];
    }
    if(s1[i-1] == s2[j-1]){
        dp[i][j] = Solve4(s1,s2,i-1,j-1,dp)+1;
        return dp[i][j];
    }
    dp[i][j] = max(Solve4(s1,s2,i-1,j,dp),Solve4(s1,s2,i,j-1,dp));
    return dp[i][j];
}

int main(){
    char s1[20] = "abcdef";
    char s2[20] = "dgajchdef";
    int dp[20][20];
    memset(dp, -1, sizeof(dp));
    Solve1(s1,s2);
    Solve2(s1,s2);
    Solve3(s1,s2);
    printf("Solve4:%d",Solve4(s1,s2,strlen(s1),strlen(s2),dp));
    return 0;
}

二、距離の編集
LeetCode原題:
72. Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character b) Delete a character c) Replace a character
繰返し式:
dp[i][j]は長さiと長さjの文字列の編集距離を表し、原題であるword 1(2)の前のi(j)文字からなる文字列に対応する.
dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1                            if  word1[i-1] != word2[j-1]
dp[i][j] = dp[i-1][j-1]                                                                    if  word1[i-1] == word2[j-1]
dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+word 1[j-1]=word 2[j-1]?0:1)と書くこともできますが、word 1[i-1]==word 2[j-1]の場合もdp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+word 1[i-1]+word 1[i-1]=word 2[j-1]の場合もdp[i][j]=dp[i][j-1]=dp[i][j-1[j-1]=dp[j-1[成立!!!
次は些細な考えですが、無視できます.
dp[i-1][j-1]+word 1[i-1]=word 2[j-1]?0:1が必ずdp[i-1][j]+1,dp[i][j-1]+1以下になるかどうかは,成立すれば動的計画は貪欲アルゴリズムになるが,成立せず,反例を見つけることができる.以下の証明からも答えが得られます.
まず、dp[i-1][j-1]<=dp[i-1][j]+1を証明する.
w 1'はdp[i-1][j]ステップを経てw 2に可変となり、w 2末位文字を削除してw 2'を得るため、dp[i-1][j]+1を経てw 2'に変換できず、dp[i-1][j-1]はw 1'、w 2'の編集距離となるため、dp[i-1][j]+1>=dp[i-1][j-1]は必ず成立するので、第2の繰返し式のようにdp[i-1][j]+1、dp[i][j-1]+1、dp[i-1][j-1]を比較する必要はない.
dp[i-1][j-1]<=dp[i-1][j]は必ず成立しますか?
dp[i-1][j-1]
二つの答えはどちらも違います!簡単な反例:word 1="A",word 2="A",dp[1][0]=1,dp[1][1]=0,dp[i-1][j-1]>dp[i-1][j]
まとめ:dp[i-1][j-1]<=dp[i-1][j]+1と等号が成立
以上はdp[i-1][j-1]とdp[i-1][j]の直接的な大きさを比較しただけであり、dp[i][j]がどのような場合にdp[i-1][j-1]と等しいかは議論されていない.
以下は正式な証明の繰返し式です.
文字列w 1、w 2の長さをそれぞれi、jとし、w 1、w 2の末尾文字が同じであるw 1[i-1]=w 2[j-1]、w 1の前i-1文字からなる文字列をw 1'、w 2の前j-1文字からなる文字列をw 2'、w 1、w 2の編集距離をdp[i][j]、w 1'とw 2の編集距離をdp[i-1][j]、w 1'とw 2'の編集距離をdp[i-1][j]とする.

int min(int a, int b){
    return a