1143. 最长公共子序列

1035. 不相交的线

这两题一样

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

53. 最大子数组和

每一个点两种选择，加前面的一个 或 从当前开始

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