33OJ
登录 注册

1 条题解

  • 2
    @ 2026-11-8 21:56:30

    这道题很简单 一个普通的dp就过了,代码放下面,各位自己看

    #include<bits/stdc++.h>
    using namespace std;
    const int N = 1010;
    string s1,s2;
    int dp[N][N];
    int main()
    {
    	cin>>s1>>s2;
    	for(int i = 1;i<=s1.size();i++)
    	{
    		dp[i][0] = i;
    	}
    	for(int i = 1;i<=s2.size();i++)
    	{
    		dp[0][i] = i;
    	}
    	for(int i = 1;i<=s1.size();i++)
    	{
    		for(int j = 1;j<=s2.size();j++)
    		{
    			if(s1[i-1] == s2[j-1])
    			{
    				dp[i][j] = dp[i-1][j-1];
    			}
    			else
    			{
    				dp[i][j] = min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
    			}
    		}
    	}
    	cout<<dp[s1.size()][s2.size()];
    	return 0;
    }
    
    

    信息

    ID
    7
    时间
    1000ms
    内存
    256MiB
    难度
    显示难度普及
    标签
    递交数
    8
    已通过
    4
    上传者