题解 | 最长公共子序列(一) 栈帧最大只能放1MB数据，超过放外面当全局变量

int dp[1002][1002];
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串
     * @param s2 string字符串
     * @return int整型
     */
    
    int LCS(string s1, string s2) {

        // 最小问题的情况
        for (int j = 0; j <= s1.size(); j++) {
            dp[0][j] = 0;  // s1前缀为0 所以最大公共子序列长度为0
        }
        for (int i = 0; i <= s2.size(); i++) {
            dp[i][0] = 0;  // s2前缀为0 所以最大公共子序列长度为0
        }

        // 大问题 -> 小问题
        for (int i = 1; i <= s1.size(); i++) {
            for (int j = 1; j <= s2.size(); j++) {
                // s1[0] -> s1[i-1] 和 s2[0] -> s2[j-1]
                if (s1[i - 1] == s2[j - 1]) {
                    // 第i个字符相同
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 第i/j个字符(下标为i-1/j-1)不同，取两者之间较大的
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }

        return dp[s1.size()][s2.size()];
    }
};