1. 初始化动态规划数组 dp

动态规划数组 dp 是一个二维数组，其大小为 (text1.size() + 1) x (text2.size() + 1)，dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符之间最长公共子序列的长度。初始化所有元素为 0。

2. 遍历字符串进行动态规划填表

通过两层循环遍历两个字符串的每个字符，外层循环变量 i 从 1 遍历到 text1.size()，内层循环变量 j 从 1 遍历到 text2.size()。这里的 i 和 j 用于表示考虑字符串 text1 的前 i 个字符和字符串 text2 的前 j 个字符时的情况。

3. 状态转移方程

• 匹配情况：当 text1[i - 1] == text2[j - 1] 时，说明当前 i 和 j 指向的字符匹配，那么 dp[i][j] 应该是不包含这两个字符的前一个状态 dp[i - 1][j - 1] 加上这一对匹配字符带来的长度 1。
• 不匹配情况：当 text1[i - 1] != text2[j - 1] 时，说明当前 i 和 j 指向的字符不匹配，那么 dp[i][j] 应该是 dp[i-1][j] 和 dp[i][j-1] 中的最大值，分别表示不包含 text1 的第 i 个字符或不包含 text2 的第 j 个字符时的最长公共子序列的长度。

4. 返回结果

经过动态规划填表后，dp[text1.size()][text2.size()] 存储的就是 text1 和 text2 的最长公共子序列的长度，这就是最终的结果。

#include <iostream>
#include <string>
#include <vector>

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

int main() {
    Solution solution;
    std::string text1 = "abcde";
    std::string text2 = "ace";
    std::cout << "Longest Common Subsequence Length: " << solution.longestCommonSubsequence(text1, text2) << std::endl;
    return 0;
}

本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！

那么本题就和刚才这道题动态规划：1143.最长公共子序列就是一样一样的了。一样到什么程度呢？ 把字符串名字改一下，其他代码都不用改，直接copy过来就行了。

class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
        for (int i = 1; i <= A.size(); i++) {
            for (int j = 1; j <= B.size(); j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[A.size()][B.size()];
    }
};

动规五部曲如下：

1. 确定dp数组（dp table）以及下标的含义

dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。

1. 确定递推公式

dp[i]只有两个方向可以推出来：

• dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
• nums[i]，即：从头开始计算当前连续子序列和

一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

1. dp数组如何初始化

从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。

dp[0]应该是多少呢?

根据dp[i]的定义，很明显dp[0]应为nums[0]即dp[0] = nums[0]。

1. 确定遍历顺序

递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。

1. 举例推导dp数组

以示例一为例，输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，对应的dp状态如下：

注意最后的结果可不是dp[nums.size() - 1]！ ，而是dp[6]。

在回顾一下dp[i]的定义：包括下标i之前的最大连续子序列和为dp[i]。

那么我们要找最大的连续子序列，就应该找每一个i为终点的连续最大子序列。

所以在递推公式的时候，可以直接选出最大的dp[i]。

#include <iostream>
#include <vector>

class Solution {
public:
    int maxSubArray(std::vector<int>& nums) {
        std::vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = std::max(dp[i - 1] + nums[i], nums[i]);
            result = std::max(result, dp[i]);
        }
        //print dp
        // for (int i: dp) {
        //     std::cout << i << ",";
        // }
        return result;
    }
};

int main() {
    std::vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};
    Solution sol ;
    int res = sol.maxSubArray(nums);
    // std::cout << std::endl;
    std::cout << res << std::endl;
    return 0;

}