关于dp算法的一个bug需要修改

Question

这是·一道动态规划问题

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

int edit(char *s1,char *s2)
{
    int i,j;
    int m = strlen(s1);
    int n = strlen(s2);
    int dp[m+1][n+1];

    for(i = 0;i < m+1;i++)
    {
        dp[i][0] = i;
    }

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

    for(i = 1;i < m+1;i++)
    {
        for(j = 1;j < n+1;j++)
        {
            if(s1[i-1] = s2[j-1])
            dp[i][j] = dp[i-1][j-1];

            else
            {
                dp[i][j] = ((dp[i-1][j]<dp[i][j-1])?dp[i-1][j]:dp[i][j-1])+1;
            }
        }
    }

    return dp[m][n];

}

void Similar(char *S,int n,char *T[])
{
    int i,j;
    int count[n];
    for(i = 0;i < n;i++)
    {
        count[i]  =  edit(S,T[i]);
    }


    for(i = 0;i < n;i++)
    {
        for(j = 0;j < n-i-1;j++)
        {
            int temp;
            if(count[j]>count[j+1])
            {
                temp = count[j];
                count [j] = count[j+1];
                count[j+1] = temp;
            }

            char *Temp[51];
            {
                strcpy(Temp,T[j]);
                strcpy(T[j],T[j+1]);
                strcpy(T[j+1],Temp);
            }
        }
    }


    for(i = 0;i <n;i++)
    {
        printf("%s",T[i]);
    }


    
}

int main()
{
    char S[51];
    int n;
    scanf("%s",S);
    scanf("%d",&n);
    char *T[n];
    for(int i=0;i<n;i++)
    {
        scanf("%s",T[i]);
    }

    Similar(S,n,T);
    return 0;

}

结果却是这样，到底是哪里的问题

Answer 1

【以下回答由 GPT 生成】

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

int edit(char *s1, char *s2) {
    int i, j;
    int m = strlen(s1);
    int n = strlen(s2);
    int dp[m+1][n+1];

    for (i = 0; i < m+1; i++) {
        dp[i][0] = i;
    }

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

    for (i = 1; i < m+1; i++) {
        for (j = 1; j < n+1; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            }
            else {
                dp[i][j] = ((dp[i-1][j] < dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1]) + 1;
            }
        }
    }
    return dp[m][n];
}

void Similar(char *S, int n, char *T[]) {
    int i, j;
    int count[n];
    for (i = 0; i < n; i++) {
        count[i] = edit(S, T[i]);
    }

    for (i = 0; i < n; i++) {
        for (j = 0; j < n-i-1; j++) {
            int temp;

            if (count[j] > count[j+1]) {
                temp = count[j];
                count[j] = count[j+1];
                count[j+1] = temp;

                char Temp[51];
                strcpy(Temp, T[j]);
                strcpy(T[j], T[j+1]);
                strcpy(T[j+1], Temp);
            }
        }
    }

    for (i = 0; i < n; i++) {
        printf("%s ", T[i]);
    }
    printf("\n");
}

int main() {
    char S[51];
    printf("Enter a string: ");
    fgets(S, sizeof(S), stdin);
    S[strcspn(S, "\n")] = '\0';

    int n;
    printf("Enter the number of strings: ");
    scanf("%d", &n);
    getchar(); // Capture the newline character after scanf

    char T[n][51];
    for (int i = 0; i < n; i++) {
        printf("Enter string %d: ", i + 1);
        fgets(T[i], sizeof(T[i]), stdin);
        T[i][strcspn(T[i], "\n")] = '\0';
    }

    Similar(S, n, T);
    return 0;
}

修复后的代码主要做了以下几个改动： 1. 在 main 函数中添加代码，让用户输入字符串 S 和字符串个数 n，分别存储到数组 S 和二维数组 T 中。 2. 将 char *Temp[51]; 修改为 char Temp[51];，修复了字符串交换的 Bug。 3. 在 Similar 函数的最后添加了换行符以及修改了 printf 函数，将结果字符串依次输出。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^