【C++编程能力提升】

一、300 最长递增子序列

题目链接：300 最长递增子序列

核心：dp[i]表示以i结尾的数组的最长递增子序列，状态转移方程是当前元素i需要与0~i-1元素比较，只有当前元素i较大时才更新dp[i]，且取dp[i]与dp[j]+1的最大值；此外每遍历完一个元素i，需要记录当前的最大长度。

    int lengthOfLIS(vector<int>& nums) {
        //动态规划：dp[i]表示以i结尾的数组得到的最长递增子序列的长度
        int len=nums.size();
        if(len==1)  return len;
        int res=0;  //记录最长递增子序列的长度
        vector<int> dp(len,1);  //初始化为1是因为自身长度为1
        for(int i=1;i<len;i++)
        {//遍历数组各元素，从第二个元素开始，逐个与前面各元素比较
            for(int j=0;j<i;j++)
            {//遍历0~i-1元素，与i元素比较，只有i元素较大时（满足递增）才更新dp[i]
                if(nums[i]>nums[j])
                    dp[i]=max(dp[i],dp[j]+1);
            }
            if(dp[i]>res)
                res=dp[i];//更新最长递增子序列的长度
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二、674 最长连续递增序列

题目链接：674 最长连续递增序列

核心：要求递增序列是连续的，因此当前元素只需与前一个元素比较即可，只有在当前元素较大时更新dp[i]值，并记录每个元素对应长度的最大值。
该题比300 最长递增子序列更为简单。

    int findLengthOfLCIS(vector<int>& nums) {
        //要求连续递增，只需比较当前元素i与前一个元素i-1的大小
        int len=nums.size();
        if(len<=1)  return len;  //遍历从第二个元素开始，故需提前判断只有0、1个元素的情况
        int res=0;
        vector<int> dp(len,1);
        for(int i=1;i<len;i++)
        {//遍历数组各元素，只有当前元素大于前一个元素时，才满足递增，更新dp[i]
            if(nums[i]>nums[i-1])  
                dp[i]=dp[i-1]+1;
            if(dp[i]>res)
                res=dp[i];  //每次更新完dp[i]后都需要记录最大值
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

三、718 最长重复子数组

题目链接：718 最长重复子数组

核心：涉及两个数组，考虑使用二维dp数组，重复子数组说明子数组是连续的，也就是说当前元素只需与前一个元素比较大小。
dp[i][j]表示以i-1结尾的nums1数组和以j-1结尾的nums2数组的最长重复子数组长度，如果两个数组的前一个元素对应相同，则说明此元素重复，那么更新dp[i][j]=dp[i-1][j-1]+1，否则不相同则说明该元素无法与前面的重复子数组构成新的重复子数组，即不更新dp值。

    int findLength(vector<int>& nums1, vector<int>& nums2) {
        //动态规划，dp[i][j]表示nums1的i-1结尾与nums2的j-1结尾的最长重复子数组长度
        int len1=nums1.size();
        int len2=nums2.size();
        vector<vector<int>> dp(len1+1,vector<int> (len2+1,0));
        int res=0;
        for(int i=1;i<=len1;++i)
        {//遍历nums1各元素
            for(int j=1;j<=len2;++j)
            {//遍历nums2各元素
                if(nums1[i-1]==nums2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;    //前一个元素对应相等，则更新当前元素dp值
                if(dp[i][j]>res)
                    res=dp[i][j];   //记录最大长度
            }
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18