题解 | #最长公共子序列(一)#

最长公共子序列(一)

https://www.nowcoder.com/practice/672ab5e541c64e4b9d11f66011059498

#include <bits/stdc++.h>

using namespace std;

//4MB,超过局部变量的内存了,变成全局变量=>new申请堆空间
int dp[1002][1002];//dp[i][j] s1的前i个元素, s2的前j个元素 的最大公共长度

int main() {
    int n;
    int m;
    char s1[1001];
    char s2[1001];
    scanf("%d%d", &n, &m);
    scanf("%s%s", &s1, &s2);


    //初始化小问题
    for (int j = 0; j <= m; ++j) {
        dp[0][j] = 0;
    }
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = 0;
    }

    //
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            //s1[0]~s1[i-1]和s2[0]~s2[j-1]
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    std::cout << dp[n][m] << std::endl;
    return 0;
}

全部评论

相关推荐

07-02 18:09
门头沟学院 Java
苍穹外卖和谷粒商城这俩是不是烂大街了,还能做吗?
想去重庆的鸽子在吐槽:你不如把这俩做完自己搞明白再优化点再来问 何必贩卖焦虑
点赞 评论 收藏
分享
06-16 15:04
黑龙江大学 Java
零OFFER战士:另一个版本查看图片
点赞 评论 收藏
分享
VirtualBoo...:都去逗他了?
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 14:23
steelhead:你回的有问题,让人感觉你就是来学习的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务