【C++编程能力提升】

一、1143 最长公共子序列

题目链接：1143 最长公共子序列

核心：两个数组的公共子序列，首先考虑使用二维dp数组，dp[i][j]表示以i-1结尾的text1和以j-1结尾的text2的最长公共子序列长度；其次子序列未要求连续，因此当前dp[i][j]可能存在两种情况，要么前一个元素相同，即存在公共元素，那么dp[i][j]=dp[i-1][j-1]+1，否则不存在公共元素则延续前一个元素的最长公共子序列dp[i][j]=max(dp[i-1][j],dp[i][j-1])。

    int longestCommonSubsequence(string text1, string text2) {
    //动态规划：dp[i][j]表示以i-1结尾的text1和以j-1结尾的text2的最长公共子序列长度
        int len1=text1.size();
        int len2=text2.size();
        vector<vector<int>> dp(len1+1,vector<int> (len2+1,0));
        for(int i=1;i<=len1;++i)
        {
            for(int j=1;j<=len2;++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[len1][len2]; //遍历结束即得到最长公共子序列的长度
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二、1035 不相交的线

题目链接：1035 不相交的线

核心：两个数组不相交的线，即两个数组按顺序但不要求连续的公共子序列，因此本题就是求解最长公共子序列。

    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
//实质即求解最长公共子序列
    int len1=nums1.size();
    int len2=nums2.size();
    vector<vector<int>> dp(len1+1,vector<int> (len2+1,0));
    for(int i=1;i<=len1;++i)
    {
        for(int j=1;j<=len2;++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[len1][len2];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

三、53 最大子数组和

题目链接：53 最大子数组和

核心：此题可用贪心求解，注意是和小于0时需重新开始计算区间和。
同样地，dp[i]表示以i结尾的数组的最大子数组和，那么dp[i]可能是与前一个元素和当前元素组成的子数组和，也可能是当前元素值，需取其最大值；并且最大的子数组和不是在最后，而是可能在中间，因此对于每一个i都需要更新最大子数组和的值。

    int maxSubArray(vector<int>& nums) {
//动态规划：dp[i]表示以i结尾的元素nums[i]的最大子数组和
    if(nums.size()==0) return 0;
    vector<int> dp(nums.size(),0);
    dp[0]=nums[0];
    int res=dp[0];
    for(int i=1;i<nums.size();++i)
    {//遍历数组各元素，从第二个元素开始
        dp[i]=max(nums[i],dp[i-1]+nums[i]); //要么是包括i的子数组和，要么重新开始累加
        if(res<dp[i])
            res=dp[i];  //记录最大子数组和的值
    }
    return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14