LeetCode 1143最长公共子序列 1035不相交的线 53最大子序和 | 代码随想录25期训练营day53

动态规划算法11

LeetCode 1143 最长公共子序列 2023.12.16

• 题目链接
• 代码随想录讲解[链接]
  

int longestCommonSubsequence(string text1, string text2) {
    //1确定dp二维数组，dp[i][j]表示以text1[i-1]、text2[j-1]结尾相同的公共子序列的最大长度
    vector<vector<int>> dp(text1.size()+1, vector<int>(text2.size()+1, 0));
    //3初始化，第一行和第一列必须初始化，意义上为0，因为遍历开始从text1[0]与text2[0]比较
    //2确定递推公式，4确定遍历顺序
    //顺序遍历
    for (int i = 1; i <= text1.size(); i++)
    {
        for(int j = 1; j <= text2.size(); j++)
        {
            //如果text1[i-1]、text2[j-1]相同,那么dp[i-1][j-1]+1
            if(text1[i-1] == text2[j-1])
                dp[i][j] = dp[i-1][j-1]+1;
            //如果text1[i-1]、text2[j-1]不相同,
            //那么dp[i][j]=max(i-1长度text1与j长度text2最大长度，i长度text1与j-1长度text2最大长度)
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    //因为dp[i][j]连续赋值，那么最终答案一定为dp[text1.size()][text2.size()]
    return dp[text1.size()][text2.size()];
}

LeetCode 1035 不相交的线 2023.12.16

• 题目链接
• 代码随想录讲解[链接]
  

int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
    //此题实际就是求最长公共子序列，按顺序可以不连续的相同子序列的最大长度
    //1确定dp二维数组，dp[i][j]表示以nums1[i-1]、nums2[j-1]结尾相同的公共子序列的最大长度
    vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1, 0));
    //3初始化，第一行和第一列必须初始化，意义上为0，因为遍历开始从nums1[0]与nums2[0]比较
    //2确定递推公式，4确定遍历顺序
    //顺序遍历
    for (int i = 1; i <= nums1.size(); i++)
    {
        for(int j = 1; j <= nums2.size(); j++)
        {
            //如果nums1[i-1]、nums2[j-1]相同,那么dp[i-1][j-1]+1
            if(nums1[i-1] == nums2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            //如果nums1[i-1]、nums2[j-1]不相同,
            //那么dp[i][j]=max(i-1长度nums1与j长度nums2最大长度，i长度nums1与j-1长度nums2最大长度)
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[nums1.size()][nums2.size()];
}

LeetCode 53 最大子序和 2023.12.16

• 题目链接
• 代码随想录讲解[链接]
  

int maxSubArray(vector<int>& nums) {
    //贪心算法
    /*
        //cur记录当前连续子数组和，当cur<0时，贼将cur归0，持续遍历
        int cur = 0;
        //result存储最终答案，连续子数组最大和
        int result = INT_MIN;
        //开始遍历
        for (int i = 0; i < nums.size(); i++)
        {
            //求连续子数组的和
            cur += nums[i];
            //判断与result关系，若比result大，则更新最大值到result中
            result = cur > result ? cur : result;
            //如果连续子数组的和cur小于0，则归0后持续下一次遍历
            if(cur < 0)
                cur = 0;
        }
        return result; */ 

    //动态规划算法
    //创建变量result存储最大子数组和，初始值为nums[0]
    int result = nums[0];
    //1确定dp数组，dp[i]表示以nums[i]结尾的连续子数组的最大和
    vector<int> dp(nums.size(), 0);
    //3初始化，dp[0]=nums[0]，其他值初始化为0
    dp[0] = nums[0];
    //2确定递推公式，4确定遍历顺序
    for (int i = 1; i < nums.size(); i++)
    {
        dp[i] = max(dp[i-1] + nums[i], nums[i]);
        //因为存在负数，所以dp[i]可能变小，所以将最大值保存在result中
        if(dp[i] > result)
            result = dp[i];
    }
    return result;
}