300.最長遞增子序列
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.size() <= 1) return nums.size();
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;
}
};
674. 最長連續遞增序列
總結:不連續遞增子序列的跟前0-i 個狀态有關,連續遞增的子序列隻跟前一個狀态有關
注意:
i < nums.size() - 1;
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
if (nums.size() == 0) return 0;
int result = 1;
vector<int> dp(nums.size() ,1);
for (int i = 0; i < nums.size() - 1; i++) {
if (nums[i + 1] > nums[i]) { // 連續記錄
dp[i + 1] = dp[i] + 1;
}
if (dp[i + 1] > result) result = dp[i + 1];
}
return result;
}
};
718. 最長重複子數組
總結:
dp[i][j] = dp[i - 1][j - 1] + 1;
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
vector<vector<int>> dp (A.size() + 1, vector<int>(B.size() + 1, 0));
int result = 0;
for (int i = 1; i <= A.size(); i++) {
for (int j = 1; j <= B.size(); j++) {
if (A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
if (dp[i][j] > result) result = dp[i][j];
}
}
return result;
}
};
滾動數組 二維變一維數組
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
vector<int> dp(vector<int>(B.size() + 1, 0));
int result = 0;
for (int i = 1; i <= A.size(); i++) {
for (int j = B.size(); j > 0; j--) {
if (A[i - 1] == B[j - 1]) {
dp[j] = dp[j - 1] + 1;
} else dp[j] = 0; // 注意這裡不相等的時候要有賦0的操作
if (dp[j] > result) result = dp[j];
}
}
return result;
}
};
1143.最長公共子序列
總結:
dpi:長度為[0, i - 1]的字元串text1與長度為[0, j - 1]的字元串text2的最長公共子序列為dpi
dpi = dpi - 1 + 1; dpi = max(dpi - 1, dpi);
錯誤:i <= text1.size(); j <= text2.size()
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
for (int i = 1; i <= text1.size(); i++) {
for (int j = 1; j <= text2.size(); j++) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[text1.size()][text2.size()];
}
};
1035.不相交的線
總結:
啊 竟然和上一個一模一樣,換個模闆就不認識了。
class Solution {
public:
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
for (int i = 1; i <= A.size(); i++) {
for (int j = 1; j <= B.size(); j++) {
if (A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[A.size()][B.size()];
}
};
53. 最大子序和
總結:
錯誤:dp[0] = nums[0];
int result = dp[0]; 初始化為0
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.size() == 0) return 0;
vector<int> dp(nums.size());
dp[0] = nums[0];
int result = dp[0];
for (int i = 1; i < nums.size(); i++) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 狀态轉移公式
if (dp[i] > result) result = dp[i]; // result 儲存dp[i]的最大值
}
return result;
}
};
- 時間複雜度:O(n)
- 空間複雜度:O(n)
392.判斷子序列
dpi 表示以下标i-1為結尾的字元串s,和以下标j-1為結尾的字元串t,相同子序列的長度為dpi。
class Solution {
public:
bool isSubsequence(string s, string t) {
vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); j++) {
if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = dp[i][j - 1];
}
}
if (dp[s.size()][t.size()] == s.size()) return true;
return false;
}
};
- 時間複雜度:O(n × m)
- 空間複雜度:O(n × m)