LeetCode 1143 Longest Common Subsequence

概述

https://leetcode.com/problems/longest-common-subsequence/

动态规划法

极值问题，无脑动态规划。

class Solution {
public:
    vector<vector<int>> dp;
    string text1;
    string text2;
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size(), vector<int>(text2.size(), -1));
        this->dp = dp;
        this->text1 = text1;
        this->text2 = text2;
        return helper(0, 0);
    }
    
    int helper(int i, int j) {
        if (i >= text1.size() || j >= text2.size()) return 0;
        if (dp[i][j] != -1) return dp[i][j];
        if (text1[i] == text2[j]) {
            dp[i][j] = 1 + helper(i+1, j+1);
        } else {
            dp[i][j] = max(helper(i+1, j), helper(i, j+1));
        }
        return dp[i][j];
    }
};