300.最长递增子序列
代码随想录链接
题目
LeetCode-300.最长递增子序列
在给定的整数数组中找出严格递增子序列的长度.
题目分析
拿回溯写了一下, 但是超时, 还得DP.
动态规划五部曲:
dp数组及下标的含义
dp[i]代表在第i位及之前的数组中最长递增子序列的长度.
递推公式
位置i最长升序子序列等于与前面各位小于i处的值的位置的最长升序子序列的长度+1的最大值
1
2
| if (nums[i] > nums[j])
dp[i] = max(dp[i], dp[j] + 1);
|
dp数组初始化
每个位置的最长子序列的长度都大宇等于1,
故所有位置的值均应被初始化为1.
确定遍历顺序
dp[i]的结果都由[0, i - 1]的状态推到而来,
所以遍历顺序一定是由前向后遍历.
因为要取最大值, 所以还需要一个内层for循环来求最大值
题解
动态递归做法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.size() == 1)
return 1;
vector<int> dp(nums.size(), 1);
int result = 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);
}
if (dp[i] > result)
result = dp[i];
}
return result;
}
};
|
回溯做法:(超时⚠️)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
private:
int maxLen = 0;
vector<int> seq;
void backtracing(vector<int> &nums, int startIndex) {
if (seq.size () > maxLen)
maxLen = seq.size();
if (startIndex >= nums.size()) {
return;
}
for (int i = startIndex; i < nums.size(); i++)
if (!seq.size() || nums[i] > seq.back()) {
seq.push_back(nums[i]);
backtracing(nums, i + 1);
seq.pop_back();
}
}
public:
int lengthOfLIS(vector<int>& nums) {
backtracing(nums, 0);
return maxLen;
}
};
|
674.最长连续递增序列
代码随想录链接
题目
LeetCode-674.最长连续递增序列
给定未经排序的数组, 返回最长的连续递增的子序列的长度.
题目分析
动态规划五部曲:
确定dp数组及下标的含义
dp[i]表示第[0, i]位最长的连续递增的子序列的长度.
递推公式
由于是求连续递增,
所以每个位置上只需要判断与前一个位置的关系即可根据前一位的状态计算出当前位的数据.
1
2
| if (nums[i] > nums[i - 1])
dp[i] = dp[i - 1] + 1;
|
dp数组的初始化
和上一题一样, 对于每一位来说,
最长连续递增子序列的长度都至少是1.
遍历顺序
同理可知应从前向后.
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int result = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] > nums[i - 1])
dp[i] = dp[i - 1] + 1;
if (dp[i] > result)
result = dp[i];
}
return result;
}
};
|
718.最长重复子数组
代码随想录链接
题目
LeetCode-718.最长重复子数组
给定两个整数数组, 求两者最长公共子序列的长度.
题目分析
动态规划五部曲:
dp数组及下标含义
dp[i][j]表示以i下标为结尾的A, 和以j下标为结尾的B,
最长公共子序列长度.
递推公式
当nums1[i] == nums2[j]时, dp[i][j] = dp[i - 1][j - 1] + 1;
dp数组的初始化
因为递推公式是根据对上一位的结果得出的,
故应该将两个数组的第一位先填充好,
即dp[0][j]和dp[i][0]先根据nums1[i]和nums2[j]是否对应先填充好.
遍历顺序
两层for循环, 一层遍历A, 一层遍历B.
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
int result = 0;
for (int i = 0; i < nums1.size(); i++)
if (nums1[i] == nums2[0])
dp[i][0] = 1;
for (int j = 0; j < nums2.size(); j++)
if (nums2[j] == nums1[0])
dp[0][j] = 1;
for (int i = 0; i < nums1.size(); i++)
for (int j = 0; j < nums2.size(); j++) {
if (nums1[i] == nums2[j] && i && j)
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > result)
result = dp[i][j];
}
return result;
}
};
|
