文章

68

粉丝

691

获赞

26

访问

577.8k

头像
经典dp

 

#define ll long long
#define vec vector<int>
#define inf 0x3f3f3f3f
#define MAX 1005
#define P pair<ll,ll>
#define MOD 1000000

int main() {
	string a, b;
	int dp[MAX][MAX];
	while (cin >> a >> b) {
		a = ' ' + a, b = ' ' + b;
		int l1 = a.size(), l2 = b.size();
		for (int i = 0; i < l1; i++)
			dp[i][0] = i;
		for (int j = 0; j < l2; j++)
			dp[0][j] = j;
		for (int i = 1; i < l1; i++)
			for (int j = 1; j < l2; j++) {
				if (a[i] == b[j])
					dp[i][j] = min(1 + dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1]));
				else
					dp[i][j] = 1 + min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1]));
			}
		cout << dp[l1 - 1][l2 - 1] << endl;
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发