问题描述 链接到标题

1143.最长公共子序列

解题思路 链接到标题

dp[i][j]表示text1的前i个字符和text2的前j个字符里最长公共子序列长度:

  • if (text[i - 1] == text2[j - 1]), dp[i][j] = dp[i - 1][j - 1] + 1;
  • if (text[i - 1] != text2[j - 1]), dp[i][j] = max(dp[i - 1][j], dp[i][j - ]);

代码 链接到标题 

#include <string>
#include <vector>
using std::string;
using std::vector;
class Solution {
  public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
        int m = 0;
        int res = 0;
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    //dp[i][j] = max(dp[i - 1][j - 1] + 1, max(dp[i - 1][j], dp[i][1]));
                    dp[i][j] = dp[i - 1][j - 1] + 1; // 这里必须保证，假设m = dp[a][b], 必须a, b分别小于i, j才行
                } else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[text1.size()][text2.size()];
    }
};