代码随想录算法训练营Day52 | 300.最长递增子序列、674.最长连续递增序列、718.最长重复子数组

300.最长递增子序列

这题的重点是DP数组的定义，子序列必须以nums[i]为最后一个元素，这样dp数组中后面的元素才能与前面的元素进行对比

1、DP数组定义：dp[i]表示以nums[i]为最后一个元素的最长递增子序列长度

2、DP数组初始化：全部初始化为1（子序列最少也有自身一个）

3、递推公式：与 i 前所有元素进行对比，如果nums[i] > nums[j]，那么更新dp[i]

        · 基本——dp[j]：位置 j 处的最长递增子序列

        · 新增—— +1：算上nums[i]，多了一个递增元素

        · 最后的递推公式：dp[i]取较大值：dp[i] = std::max(dp[i], dp[j] + 1)

4、遍历顺序：从前向后遍历

int lengthOfLIS(vector<int>& nums) {// dp[i]表示以nums[i]为最后一个元素的最长递增子序列长度// 全部初始化为1（子序列最少也有自身一个）vector<int> dp(nums.size(), 1);int ans = 1;for (int i = 1; i < nums.size(); ++i) {// 与i之前的所有元素做比较for (int j = 0; j < i; ++j) {// 不断更新dp[i]，寻找以nums[i]为最后一个元素的最长递增子序列长度if (nums[i] > nums[j])dp[i] = std::max(dp[i], dp[j] + 1);}// 记录过程中的最长子序列if (dp[i] > ans)ans = dp[i];}return ans;
}

 674.最长连续递增序列

 整体和上一题差不多，但由于要求是“连续”子序列，所以简单不少。主要差别在遍历过程中，为了保持序列连续，只需要与前一个元素对比即可（上一题需要与前面所有元素对比）。

int findLengthOfLCIS(vector<int>& nums) {vector<int> dp(nums.size(), 1);int ans = 1;for (int i = 1; i < nums.size(); ++i) {// 只需要与 i - 1 比较if (nums[i] > nums[i - 1]) {dp[i] = dp[i - 1] + 1;ans = std::max(ans, dp[i]);}}return ans;
}// 压缩空间写法
iint findLengthOfLCIS(vector<int>& nums) {int dp = 1;int ans = 1;for (int i = 1; i < nums.size(); ++i) {if (nums[i] > nums[i - 1])ans = std::max(ans, ++dp);elsedp = 1;}return ans;
}

718.最长重复子数组

写暴力超时了，剪剪枝可能有机会过？

int findLength0(vector<int>& nums1, vector<int>& nums2) {// 尝试用哈希表来加快索引// key：值// value：出现值的下标unordered_map<int, vector<int>> mapNum2;for (int i = 0; i < nums2.size(); ++i) {auto it = mapNum2.find(nums2[i]);if (it == mapNum2.end())mapNum2.insert({ nums2[i], {i} });elseit->second.push_back(i);}vector<int> dp(nums1.size(), 0);int ans = 0;// 暴力两层循环 + 最内层判断重复子序列长度for (int i = 0; i < nums1.size(); ++i) {auto it = mapNum2.find(nums1[i]);if (it == mapNum2.end())continue;ans = std::max(ans, 1);for (int k : it->second) {int len = 1;for (int j = 1; i + j < nums1.size() && k + j < nums2.size(); ++j) {if (nums1[i + j] == nums2[k + j]) {dp[i + j] = std::max(dp[i + j], ++len);ans = std::max(ans, dp[i + j]);}elsebreak;}}}return ans;
}

动规写法：

这题重点也是DP数组的定义：两个序列所以DP数组用二维

1、DP数组定义：两个维度表示两个数组的索引，dp[i][j]表示以nums1[i - 1]和nums2[j - 1]为结尾的两个字符串的最长重复子数组长度

        （子序列问题一般都定义为 i - 1 和 j - 1，目的是精简初始化的步骤）

2、DP数组初始化：首行与首列元素无意义，但为了递推公式将其初始化为0，其余元素随意

3、递推公式：如果nums1[i - 1] == nums2[j - 1]，那么dp[i][j] = dp[i - 1][j - 1] + 1

        · 基本——dp[i - 1][j - 1]：以nums1[i - 2]和nums2[j - 1]为结尾的两个字符串的最长重复子数组长度

        · 新增—— +1：加上新的这对匹配元素

        · 最后的递推公式：dp[i] = std::max(dp[i], dp[j] + 1)

4、遍历顺序：从上到下从左到右遍历，先遍历nums1或nums2都可以

int findLength(vector<int>& nums1, vector<int>& nums2) {// dp[i][j]表示以nums1[i - 1]和nums2[j - 1]为结尾的两个字符串的最长重复子数组长度// 首行与首列元素无意义，为了递推公式将其初始化为0vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int ans = 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]递推得到dp[i][j] = dp[i - 1][j - 1] + 1;ans = std::max(ans, dp[i][j]);}}}return ans;
}