C语言 算法 动态规划 基础题

Question

题目是acwing基础算法动态规划中899.编辑距离
题目如下：

我的代码是

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

int n, m;
const int N = 15, M = 1010;
int f[N][N];
char t[M][N];

int min(int a, int b)
{
    if(a <= b) return a;
    else return b;
}

int lon(char a[],char b[])
{
    int la = strlen(a + 1), lb = strlen(b + 1);
    for (int i = 0; i <= la; i ++) f[i][0] = i;
    for (int i = 0; i <= lb; i ++) f[0][i] = i;
    
    for (int i = 1; i <= la; i ++)
        for (int j = 1; j <= lb; j ++)
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if(a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }
        return f[la][lb];
}

int main()
{
    
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i ++ ) scanf("%s", t[i] + 1);

    while(m --)
    {
        char B[M];
        int lim;
        int res = 0;
        scanf("%s%d", B + 1, &lim);
        for(int i = 0; i <= n; i ++)
            if (lon(t[i], B) <= lim) res++;
        printf("%d\n", res);
    }
    return 0;
}

感觉和y总视频里讲的一样，但是输出结果是0,4

下面是y总的代码

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 15, M = 1010;

int n, m;
int f[N][N];
char str[M][N];

int edit_distance(char a[], char b[])
{
    int la = strlen(a + 1), lb = strlen(b + 1);

    for (int i = 0; i <= lb; i ++ ) f[0][i] = i;
    for (int i = 0; i <= la; i ++ ) f[i][0] = i;

    for (int i = 1; i <= la; i ++ )
        for (int j = 1; j <= lb; j ++ )
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }

    return f[la][lb];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%s", str[i] + 1);

    while (m -- )
    {
        char s[N];
        int limit;
        scanf("%s%d", s + 1, &limit);

        int res = 0;
        for (int i = 0; i < n; i ++ )
            if (edit_distance(str[i], s) <= limit)
                res ++ ;

        printf("%d\n", res);
    }

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/62479/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

帮忙找找我的错误谢谢大家

Answer 1

以下内容由AIGC及阿里嘎多学长共同生成、有用望采纳：

---

问题分析

题目要求使用动态规划算法计算编辑距离，并根据操作次数上限判断给定的字符串中有多少个可以在限定的操作次数内通过插入、删除或替换操作变成目标字符串。

代码检查

1. 输入格式：

   • 你的代码中，读取字符串时使用了 scanf("%s", t[i] + 1);，这会导致字符串的首字符被跳过，因此实际读取的字符串长度比预期少一个字符。
   • 正确的读取方式应该是 scanf("%s", t[i]);。

2. 动态规划算法实现：

   • 你的代码中，计算编辑距离的函数 lon 存在一些问题。特别是初始化和状态转移方程的实现。
   • 正确的初始化应该是：

     for (int i = 0; i <= la; i++) f[i][0] = i;
     for (int j = 0; j <= lb; j++) f[0][j] = j;
     

   • 状态转移方程应该是：

     f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
     if (a[i - 1] == b[j - 1]) {
         f[i][j] = min(f[i][j], f[i - 1][j - 1]);
     } else {
         f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
     }
     

3. 输出格式：

   • 你的代码中，输出格式是正确的，每行输出一个整数作为结果。

修复代码

以下是修复后的代码：

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

int n, m;
const int N = 15, M = 1010;
int f[N][N];
char t[M][N];

int min(int a, int b)
{
    if(a <= b) return a;
    else return b;
}

int lon(char a[], char b[])
{
    int la = strlen(a), lb = strlen(b);
    for (int i = 0; i <= la; i++) f[i][0] = i;
    for (int j = 0; j <= lb; j++) f[0][j] = j;
    
    for (int i = 1; i <= la; i++)
        for (int j = 1; j <= lb; j++)
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if(a[i - 1] == b[j - 1]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }
    return f[la][lb];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", t[i]);

    while(m --)
    {
        char B[M];
        int lim;
        scanf("%s%d", B, &lim);
        int res = 0;
        for(int i = 0; i < n; i++)
            if (lon(t[i], B) <= lim) res++;
        printf("%d\n", res);
    }
    return 0;
}

测试代码

使用给定的输入样例进行测试：

3 2
abc
acd
bcd
ab 1
abcd 2

预期输出：

1
3

总结和反思

1. 理解题目要求：确保理解题目中的输入输出格式和算法要求。
2. 仔细检查代码：注意字符串的读取和动态规划数组的初始化。
3. 测试代码：使用不同的测试用例验证代码的正确性。
4. 学习参考代码：通过比较自己的代码和参考代码，找出差异并学习改进。

通过以上步骤，你可以更好地理解和解决这个问题，并提高你的编程技能。