#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int minimu ( int a, int b, int c );
int main (void)
{
int t,i,j;
cin>>t;
while ( t != 0 )
{
string a;
string b;
cin>>a>>b;
int k;
int len1 = a.length();
int len2 = b.length();
int dp[len1][len2];
dp[0][0] = 0;
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++ )
{
if ( a[i] == b[j] )
k = 2;
else
k = 0;
dp[i][j] = minimu(dp[i-1,j]+1,dp[i,j-1]+1,dp[i-1][j-1]+k);
}
cout<<dp[len1-1][len2-1]<<"\n";
t--;
}
return 0;
}
int minimu ( int a, int b, int c )
{
int foo = min(a,min(b,c));
return foo;
}
Run Code Online (Sandbox Code Playgroud)
这是用于在将一个字符串转换为另一个字符串时计算最小操作数的程序.唯一允许的转换操作是:
1. Deleting a character
2. Inserting a character
3. Substituting a character
Run Code Online (Sandbox Code Playgroud)
现在,当我编译这个程序时,它显示错误:
从int*到int的无效转换[-fpermissive]
在我更新二维数组的行中dp[i,j].为什么会这样?
由于声明:
int dp [len1] [len2];
dp[i-1,j]是一个数组,而不是矩阵的一个元素.(这comma operator可能令人困惑,正如@BartoszKP所解释的那样.)
也许
minimu(dp[i-1,j]+1,dp[i,j-1]+1,dp[i-1][j-1]+k);
Run Code Online (Sandbox Code Playgroud)
应该
minimu(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+k);
// ^ ^
Run Code Online (Sandbox Code Playgroud)
PS请注意,int dp[len1][len2];根据C++标准,非const大小无效,如@Cheers和hth所说.
| 归档时间: |
|
| 查看次数: |
77 次 |
| 最近记录: |