1 条题解

  • 0
    @ 2025-2-14 21:20:41

    C :

    #include <stdio.h>
    #include <string.h>
    #define min(a,b) (a<b?a:b)
    char str1[3100],str2[3100];
    int dp[3100][3100];
    int main()
    {
        int i,j,t,len1,len2;
        while(~scanf("%s%s",str1,str2))
        {
             len1 = strlen(str1);
             len2 = strlen(str2);
            for( i=0; i<=len1; i++) dp[i][0] = i;
            for( j=0; j<=len2; j++) dp[0][j] = j;
            for( i=1; i<=len1; i++)
            {
                for( j=1; j<=len2; j++)
                {
                     t = (str1[i-1] == str2[j-1])?0:1;
                    dp[i][j] = min(dp[i-1][j-1] + t, dp[i-1][j]+1);
                    dp[i][j] = min(dp[i][j],dp[i][j-1]+1);
                }
            }
            printf("%d",dp[len1][len2]);
        }
        return 0;
    }
    
    

    C++ :

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    char str1[3100],str2[3100];
    int dp[3100][3100];
    int main()
    {
        while(~scanf("%s%s",str1,str2))
        {
            int len1 = strlen(str1);
            int len2 = strlen(str2);
            for(int i=0; i<=len1; i++) dp[i][0] = i;
            for(int j=0; j<=len2; j++) dp[0][j] = j;
            for(int i=1; i<=len1; i++)
            {
                for(int j=1; j<=len2; j++)
                {
                    int t = (str1[i-1] == str2[j-1])?0:1;
                    dp[i][j] = min(dp[i-1][j-1] + t, dp[i-1][j]+1);
                    dp[i][j] = min(dp[i][j],dp[i][j-1]+1);
                }
            }
            printf("%d",dp[len1][len2]);
        }
        return 0;
    }
    

    Pascal :

    uses math;
    var s,s1:ansistring;f:array[0..2050,0..2050]of longint;i,j:longint;
    begin
      readln(s);
      readln(s1);
      for i:=1 to length(s1) do f[0,i]:=i;
      for i:=1 to length(s) do f[i,0]:=i;
      for i:=1 to length(s) do
        for j:=1 to length(s1) do
          if s[i]=s1[j] then f[i,j]:=f[i-1,j-1]
          else f[i,j]:=min(min(f[i-1,j-1]+1,f[i-1,j]+1),f[i,j-1]+1);
      writeln(f[length(s),length(s1)]);
    end.
    
    • 1

    信息

    ID
    824
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者