题解 | #最长公共子序列(一)#动态规划加滚动数组秒了

最长公共子序列(一)

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

#include <bits/stdc++.h>
//#include <iostream>
//#include <vector>
//#include <string>
//#include <algorithm>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    string s1, s2;
    cin >> s1 >> s2;
    vector<int> dp(m + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int prev = 0;  // 用来保存 dp[i-1][j-1] 的值
        for (int j = 1; j <= m;++j) {
            int temp = dp[j];  // 先保存当前 dp[j] 的值
            if (s1[i - 1] == s2[j - 1]){
                dp[j] = prev + 1;
            } else {
                dp[j] = max(dp[j], dp[j - 1]);
            }
            prev = temp;  // 更新 prev 为当前 dp[j] 的值,供下一次使用
        }
    }
    cout << dp[m] << endl;
    return 0;
}

全部评论

相关推荐

06-12 17:46
门头沟学院 Java
运营你豪哥:来说重点: ​1.项目前置,时间倒序。​​ 2.​项目描述强化结果与量化效果(STAR原则里的R)。​​ ​3.个人技能精炼,明确掌握程度,突出核心。​​ ​4.增加强有力开头的个人总结部分。​​ 5.​优化教育背景(成绩排名)、合并奖项与活动。​​
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

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