「代码随想录算法训练营」第三十七天 | 动态规划 part10

300. 最长递增子序列

题目链接:https://leetcode.cn/problems/longest-increasing-subsequence/
文章讲解:https://programmercarl.com/0300.最长上升子序列.html
题目难度:中等
视频讲解:https://www.bilibili.com/video/BV1ng411J7xP
题目状态:有思路,但是自己能写出来还是太勉强,有些细节想不到

思路:

维护一个动规数组dp[i],表示在遍历到数组中的第i个元素的时候,此时能找到的最长递增子序列的长度。

其更新的代码如下:if(num[i] > num[j]) dp[i] = max(dp[i], dp[j] + 1);

所以需要有两次遍历,i是整个数组的遍历,j是在当前元素前面的元素,这样就能确保dp[i]是当前最大的递增子序列的个数。

代码:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        vector<int> dp(nums.size(), 1);
        int ans = 0;
        for(int i = 1; i < nums.size(); ++i) {
            for(int j = 0; j < i; ++j) {
                if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
            }
            ans = ans < dp[i] ? dp[i] : ans;
        }
        return ans;
    }
};

674. 最长连续递增序列

题目链接:https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
文章讲解:https://programmercarl.com/0674.最长连续递增序列.html
题目难度:简单
视频讲解:https://www.bilibili.com/video/BV1bD4y1778v
题目状态:这题比较简单,久违的独立通过

思路:

相较于上题,这题很简单,dp数组的更新只要依靠前一个元素就可以,若当前元素大于前一个元素,就将前一个元素的dp数组加1。

代码:

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        vector<int> dp(nums.size(), 1);
        int ans = 0;
        for(int i = 1; i < nums.size(); ++i) {
            if(nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
            ans = ans < dp[i] ? dp[i] : ans;
        }
        return ans;
    }
};

贪心思路和代码:

维护一个变量count用来存放当前的连续递增序列的长度,如果遇到nums[i] > nums[i - 1]的情况,count就++,否则count就为1,记录count的最大值就可以了。

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        int ans = 0;
        int count = 1;
        for(int i = 1; i < nums.size(); ++i) {
            if(nums[i] > nums[i - 1]) count++;
            else count = 1;
            ans = ans < count ? count : ans;
        }
        return ans;
    }
};

718. 最长重复子数组

题目链接:https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
文章讲解:https://programmercarl.com/0718.最长重复子数组.html
题目难度:中等
视频讲解:https://www.bilibili.com/video/BV178411H7hV
题目状态:看题解

思路

维护一个二维动规数组d[i][j],表示在数组1中元素为i-1和数组2中元素为j-1时的最长重复子数组的大小。

若要更新这个动规数组,我们要进行嵌套循环,第一个循环是数组1,第二个循环是数组2,其更新的条件是nums1[i - 1] = nums2[j - 1],至于为什么是i-1和j-1,因为这样我们可以从1开始比较,避免处理i或j为0时的特殊情况。

代码

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        int ans = 0;
        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;
                ans = ans < dp[i][j] ? dp[i][j] : ans;
            }
        }
        return ans;
    }
};

热门相关:恶魔总裁霸道宠:老婆,太腹黑   夫人每天都在线打脸   隐婚99天:首席,请矜持   新书   终极高手