洛谷2758（字符串dp）

佚名 6年前 (2019-04-10) 随笔 838人围观抢沙发百度已收录

记得这是我初学dp时的一道题
虽说就像LCS一样搞一搞即可
但我还是写挂了qwq
SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#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;
}