四十三天打卡，今天解决子序列系列题目，定义dp[i]为以nums[i]为结尾的最长子序列长度。
300.最长递增子序列
题目链接
2024.7.12一刷
没做出来。这题答案使用dp做，答案也不是dp.back()，思路需要转换一下。
2024.9.27二刷
解题过程
- dp无思路，这题dp[i]定义为以nums[i]为结尾的最大子序列长度
- 则对于i > 0的每一个数，需比较前面所有数与nums[i]的大小，若nums[i]大则尝试更新dp[i]
if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
动态规划
class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int>dp(nums.size(), 1);int result = 1;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);}result = max(result, dp[i]);}return result;}
};
674.最长连续递增序列
题目链接
解题过程
- 用贪心做出来了，也能用动态规划做，与“300.最长递增序列”这一题的区别就是，只有前一个元素比自身小才更新dp值，而前者是需要比较前面所有元素与自身的大小。
- dp[i]的含义是：以nums[i]为结尾的最长连续递增序列长度
动态规划
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {int result = 1;vector<int>dp(nums.size(), 1);for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;result = max(result, dp[i]);}return result;}
};
718.最长重复子数组
题目链接
解题过程
- 看提示用二维数组，我们就可以定义了：
dp[i][j]是以nums1[i]和nums2[j]为结尾的两个数组的最长重复子数组，dp可以定义多一个维度，这样省去了初始化这一步。 - 状态转移公式：
if (nums[i - 1] == nums[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
动态规划
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {int result = 0;vector<vector<int>>dp(nums1.size() + 1, vector<int>(nums2.size() + 1));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;}result = max(result, dp[i][j]);}}return result;}
};
