最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

【世界独家】【算法训练营day52】LeetCode300. 最长递增子序列 LeetCode674. 最长连续递增子序列 LeetCode718. 最长重复子数组

来源：博客园

LeetCode300. 最长递增子序列

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

独上高楼，望尽天涯路

感觉和之前的动态规划思路还不一样，没有想出好的递推公式。

慕然回首，灯火阑珊处

解决这道题的重点在于将dp数组设置为：dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度。


(资料图片仅供参考)

为什么一定表示 “以nums[i]结尾的最长递增子序” ，因为我们在 做 递增比较的时候，如果比较 nums[j] 和 nums[i] 的大小，那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾， 要不然这个比较就没有意义了，不是尾部元素的比较那么 如何算递增呢。

关于状态转移方程。

注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。

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

LeetCode674. 最长连续递增子序列

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

独上高楼，望尽天涯路

和上一道题的解法异曲同工，只不过将dp[i]与dp[j]比较改成了dp[i]与dp[i-1]比较。

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

慕然回首，灯火阑珊处

思路一样。

LeetCode718. 最长重复子数组

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

独上高楼，望尽天涯路

对于二维dp数组的使用还不是很熟练。

慕然回首，灯火阑珊处

解题关键在于确定dp数组及下标的含义。

dp[i][j]：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。 （特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）

之所以dp[i][j]对应的是i-1和j-1，是为了方便初始化，如果对应的是i和j，则需要单独初始化dp[i][0]和dp[0][j]。

class Solution {public:    int findLength(vector& nums1, vector& nums2) {        vector> dp(nums1.size() + 1, vector(nums2.size() + 1, 0));        int result = 0;        for (int i = 1; i <= nums1.size(); i++) {            for (int j = 1; j <= nums2.size(); j++) {                if (nums1[i - 1] == nums2[j - 1]) {                    dp[i][j] = dp[i - 1][j - 1] + 1;                }                if (result < dp[i][j]) {                result = dp[i][j];                }            }        }        return result;    }};

关键词： 独上高楼 灯火阑珊处 望尽天涯路