【C++】23行空间优化的动态规划

class Solution {
public:
    string LCS(string str1, string str2) {
        int dp[str1.size()]; //以str1[i]、str2[j]结尾的子序列长度，以下简称sub[i][j]
        int max = 0, record = -1; //记录最大长度和str1起始位置
        for(int i = 0; i < str1.size(); i++) {
            dp[i] = str1[i] == str2[0] ? 1 : 0; //初始化sub[i][0]
        }
        for(int j = 1; j < str2.size(); j++) {
            for(int i = str1.size() - 1; i >= 1; i--) { //由于sub[i][j]需要用到sub[i-1][j-1]即dp[i-1]，倒过来循环省去存储dp[i-1]的步骤
                if(str1[i] == str2[j]) { //判断末尾字符是否相同
                    dp[i] = (i == 0 ? 1 : dp[i - 1] + 1);
                    if(dp[i] > max) { //记录最大长度和开始位置
                        max = dp[i];
                        record = i;
                    }
                }
                else dp[i] = 0;
            }
        }
        return str1.substr(record - max + 1, max);
    }
};