3061: 公共子序列 进来包看懂

解题思路:

                        不同就取右和上的最大值，相同就左上角加一，不说了，康图吧

                                          a b c f b c

                                          0 0 0 0 0 0

                                    a 0 1 1 1 1 1 1 

                                    b 0 1 2 2 2 2 2

                                    f  0 1 2 2 3 3 3

                                    c 0 1 2 3 3 3 4

                                    a 0 1 2 3 3 3 4

                                    b 0 1 2 3 3 4 4
注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 定义两个字符串变量，用于存储输入的字符串
string s1, s2;
// 定义一个二维数组dp，用于动态规划计算最长公共子序列的长度
int dp[1100][1100];
int main() {
    // 使用while循环不断读取输入的字符串对
    while (cin >> s1 >> s2) {
        // 初始化dp数组为0
        memset(dp, 0, sizeof(dp));
        // 遍历第一个字符串的每一个字符
        for (int i = 0; i < s1.size(); i++) {
            // 遍历第二个字符串的每一个字符
            for (int j = 0; j < s2.size(); j++) {
                // 如果当前字符相同，则更新dp数组的值
                if (s1[i] == s2[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    // 如果当前字符不同，则取前一步的最大值
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }
        // 输出最长公共子序列的长度
        cout << dp[s1.size()][s2.size()] << endl;
    }
    return 0;
}