动态规划（c++）

//动态规划 由于子串是连续的，只能以某个字符结尾来作为边界
//dp[i][j]表示字符串1的以i结尾的字符串，字符串2的以j结尾的公共子串
//当A[i]==A[j] dp[i][j]等于dp[i-1][j-1]+1; //当A[i]!=A[j]时，dp[i][j]=0,由于是连续的，如果此时不要求连续子串(leetcode 1143)，而是子序列，则dp[i][j]=max(dp[i-1][j],dp[i][j-1])

class Solution {
public:
    //动态规划 由于子串是连续的，只能以某个字符结尾来作为边界
    //dp[i][j]表示字符串1的以i结尾的字符串，字符串2的以j结尾的公共子串
    //当A[i]==A[j] dp[i][j]等于dp[i-1][j-1]+1;
    //当A[i]!=A[j]时，dp[i][j]=0,由于是连续的，如果此时不要求连续子串(leetcode 1143)，而是子序列，则dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    string LCS(string text1, string text2) {
        // write code here
        int len1 = text1.length();
        int len2 = text2.length();
        if (len1 == 0 || len2 == 0) {
            return 0;
        }
        vector<vector<int>> dp(len1, vector<int>(len2, 0));
        //初始化dp[0][0]
        if (text1[0] != text2[0]) {
            dp[0][0] = 0;
        }
        else {
            dp[0][0] = 1;
        }
        //初始化dp[i][0]
        for (int i = 1; i < len1; i++) {
            if (text2[0] != text1[i]) {
                dp[i][0] = 0;
            }
            else {
                dp[i][0]++;
            }
        }
        //初始化dp[0][i]
        for (int i = 1; i < len2; i++) {
            if (text1[0] != text2[i]) {
                dp[0][i] = 0;
            }
            else {
                dp[0][i]++;
            }
        }
        //动态规划判断初始化
        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                if (text1[i] == text2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else {
                    dp[i][j] = 0;
                }
            }
        }
        //记录出现最大值的位置m
        int max = 0;
        int m = 0;
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (max < dp[i][j]) {
                    max = dp[i][j];
                    m = i;
                }
            }
        }
        //初始化s，遍历m知道最大值为零，再反转字符串
        string s = "";
        while (max--) {
            s += text1[m];
            m--;
        }
        reverse(s.begin(), s.end());
        return s;
    }
};