洛谷2758（字符串dp）

记得这是我初学dp时的一道题

虽说就像LCS一样搞一搞即可

但我还是写挂了qwq

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

char s[2005], t[2005];

int dp[2005][2005];

int main() {

	scanf("%s%s", s, t);

	int n = strlen(s), m = strlen(t);

	for (int i = 0; i < n; i++)

		dp[i + 1][0] = dp[i][0] + 1;

	for (int j = 0; j < m; j++)

		dp[0][j + 1] = dp[0][j] + 1;

	for (int i = 0; i < n; i++) {

		for (int j = 0; j < m; j++) {

			if (s[i] == t[j])	dp[i + 1][j + 1] = dp[i][j];

			else {

				dp[i + 1][j + 1] = 1;

				dp[i + 1][j + 1] += min(dp[i][j], min(dp[i + 1][j], dp[i][j + 1]));

			}

		}

	}

	printf("%d\n", dp[n][m]);

	return 0;

}

巴特西

洛谷2758（字符串dp）

最新文章

热门文章