1143 最长公共子序列

思路：初始化一个大小为 (text1.size() + 1) x (text2.size() + 1) 的二维向量 dp，其中所有元素都设置为 0。两个维度中的额外 1 是为了适应空字符串作为输入的情况。

然后，它遍历 text1 和 text2 字符串中所有可能的索引对 (i, j)。如果两个字符串相应位置上的字符匹配，它将 dp[i][j] 的值更新为两个字符串前一个字符的 LCS 加上当前匹配的字符。否则，它将 dp[i][j] 的值更新为 text1 的前一个字符或 text2 的前一个字符的 LCS 中较大的那个。

最后，它返回 dp[text1.size()][text2.size()]，这代表了两个输入字符串的 LCS 的长度。

1.动态规划

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, 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] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

1035 不相交的线

思路：这道题其实和上一题一摸一样，只不过换了一种题目描述的方法，本质上还是求最长的公共子序列，所以代码也是一摸一样的

1.动态规划

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size() + 1, vector<int> (nums2.size() + 1, 0));
        for(int i = 1; i <= nums1.size(); i++){
            for(int j = 1; j <= nums2.size(); j++){
                if(nums1[i - 1] == nums2[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[nums1.size()][nums2.size()];
    }
};

53 最大子数组和

思路：这是一个用于求解给定整数数组 nums 的最大子序和的 C++ 代码。

该代码使用动态规划的思想。它首先判断输入数组是否为空，如果是，则返回 0。否则，它初始化一个大小为 nums.size() 的一维向量 dp，其中 dp[i] 表示以 nums[i] 结尾的子序列的最大和。

它将 dp[0] 初始化为 nums[0]，然后使用一个循环遍历数组 nums 中除第一个元素外的所有元素。在每个循环迭代中，它将 dp[i] 设置为 dp[i - 1] + nums[i] 和 nums[i] 中的较大值。这是因为以 nums[i] 结尾的最大子序和要么是包含 nums[i] 的前面的一个子序和加上 nums[i]，要么是 nums[i] 本身。

同时，它还记录最大子序和 result。如果当前计算的 dp[i] 大于 result，则更新 result。

最后，返回 result，即为给定数组 nums 的最大子序和。

1.动态规划

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