# 1143 - Longest Common Subsequence

解法一 - DP

這題當然也可以用暴力法或暴力+memoization，不過 DP 的 recurrence formula 其實滿直覺的，直接實作程式碼如下：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.length()+1, vector<int>(text2.length()+1));

        int maxLen = 0;
        for(int i=1; i<=text1.length(); i++) {
            for(int j=1; j<=text2.length(); j++) {
                if(text1[i-1] == text2[j-1]) {
                    dp[i][j] = 1 + dp[i-1][j-1];
                }
                else {
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }

                maxLen = max(maxLen, dp[i][j]);
            }
        }

        return maxLen;
    }
};

這個的效率就不錯：

Runtime: 12 ms, faster than 89.31% of C++ online submissions for Longest Common Subsequence. Memory Usage: 14.7 MB, less than 100.00% of C++ online submissions for Longest Common Subsequence.