算法随想Day47【动态规划】| LC1143-最长公共子序列、LC1035-不相交的线、LC53-最大子数组和

LC1143. 最长公共子序列

相对于“LC718. 最长重复子数组”，那道题是要求连续的子序列，所以出现不相等的情况时，对当前格子赋0即可。而本题不要求连续，所以不能直接赋零，而是保持跟前面一个格子值一致或者保持跟上一层同位置一样的值（两者比较大小）。

• dp[i]含义：对text2数组，以下标为 i 结尾的子序列，此时的最长重复长度

int longestCommonSubsequence(string text1, string text2)
{
    int size1 = text1.size();
    int size2 = text2.size();
    vector<vector<int>> dp(size1 + 1, vector<int>(size2 + 1, 0));
    for (int i = 1; i <= size1; ++i)
    {
        for (int j = 1; j <= size2; ++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[size1][size2];
}

LC1035. 不相交的线

与上一道的一模一样可AC，换了一个包装而已

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

LC53. 最大子数组和

之前贪心算法实现了一版，写多一版动态规划实现

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