目录
讀題
392.判断子序列
自己看到题目的第一想法
看完代码随想录之后的想法
115.不同的子序列
看完代码随想录之后的想法
392.判断子序列 - 實作
思路
原始思路
代碼隨想錄思路
Code
原始思路
代碼隨想錄思路
115.不同的子序列 - 實作
思路
Code
總結
自己实现过程中遇到哪些困难
今日收获，记录一下自己的学习时长
相關資料
392.判断子序列
115.不同的子序列
讀題
392.判断子序列
自己看到题目的第一想法
這題跟最長公共子序列基本一致，只需要將公共子序列的加法改為減法，並且在不相等的時候找最小值就好了。
看完代码随想录之后的想法
我的想法其實跟卡哥的剛好反過來，我是將所有數組初始化為s的長度，因為看到了提示是說要用到減法，但看到卡哥的做法，減法指的是刪除t的字符串，這點我把他想為是取縱向與橫向中最小的部分，雖然代碼過了，但是基本思維是不一樣的，
115.不同的子序列
看完代码随想录之后的想法
s有多少方式可以將s刪除成t，思考了很久，終於對於為甚麼是dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]，查看了許多資料後，對於這個點終於知道了，dp[i - 1][j - 1]我思考了很久，後來發現就是如果要先知道之前的比對狀況做為計算的基礎，之後我也可以不使用s[i - 1] 那我就要知道不使用s[i - 1]的比對狀況是甚麼，兩者相加，就會是s[i - 1]使用與不使用的狀況。
392.判断子序列 - 實作
思路
原始思路
-
定義DP數組以及下標的含意
dp[i][j] 代表 0~ i - 1 的t 有 0 ~ j - 1 的s 中的子序列個數為dp[i][j]
-
遞推公式
分成兩種狀態相同與不相同
不相同的話需要看之前的序列有沒有重複，之前包括兩個方面，縱向與橫向關係，要取最小的
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
相同的時候，因為之前的數都考慮過縱向與橫向的關係，可以直接從左上角減一代表有一個數包含
dp[i][j] = dp[i - 1][j - 1] - 1;
-
根據遞推公式、題意以及定義，確定DP數組如何初始化
都初始化為s.size() 如果t的子序列包含全部s，最終的dp[t.size()][s.size()] ==0 則代表不完全包含
-
確定遍歷順序
因為需要左上角的數據來進行遍歷，所以是由前往後。
代碼隨想錄思路
-
定義DP數組以及下標的含意
dp[i][j] 代表 i - 1結尾的字符串s和j - 1為結尾的字符串t，相同子序列長度為dp[i][j]
i - 1 跟 j - 1的原因是因為在做遞推時，i、j 是由 1 開始，所以要用i - 1 、 j - 1來進行定義
-
遞推公式
分成兩種狀態相同與不相同
- if (s[i - 1] == t[j - 1])
- t中找到了一个字符在s中也出現過
- 因為我的dp[i][j] 表示的是以s[i - 1]以及t[ j - 1]因為相同，所以我要在沒有當前的s[i-1] t[j - 1]的 s[i - 2] t[j - 2]的基礎上也就是dp[i - 1][j - 1] 的基礎上+1
- if(s[i - 1] ≠ t[j - 1)
- 相當於t 要刪除元素，因為 t的字符串中，這個位置並沒有s的字串，所以要刪除
- 如果是t要刪除元素，那就是取t[j - 2] 這個不包含t[ j -1]的最大值，但s是要比較的子序列，所以s不用動，也就是說這個dp[i][j]會是由s[i - 1][t - 2]所組成，所對應的dp數組是dp[i][j] = dp[i][j - 1]。
- if (s[i - 1] == t[j - 1])
-
根據遞推公式、題意以及定義，確定DP數組如何初始化
都初始化為0如果t的子序列包含全部s，最終的dp[t.size()][s.size()] ==s.size()則代表不完全包含
-
確定遍歷順序
因為需要左上角的數據來進行遍歷，所以是由前往後。
Code
原始思路
class Solution {
public:
bool isSubsequence(string s, string t) {
vector<vector<int>> dp (t.size() + 1, vector<int>(s.size() + 1, s.size()));
for(int i = 1; i < t.size() + 1; i++) {
for(int j = 1; j < s.size() + 1; j++) {
if(t[i - 1] == s[j - 1]) dp[i][j] = dp[i - 1][j - 1] - 1;
else dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
}
}
if(dp[t.size()][s.size()] == 0) return true;
else return false;
}
};
代碼隨想錄思路
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;
else return false;
}
};
115.不同的子序列 - 實作
思路
-
定義DP數組以及下標的含意
dp[i][j] 代表 i - 1結尾的字符串s的子序列中和j - 1為結尾的字符串t的各數為dp[i][j]
-
遞推公式
分成兩種狀態相同與不相同
- if (s[i - 1] == t[j - 1])
- 如果**
s[i - 1]和t[j - 1]**相等，那麼我們可以使用來匹配。 - 計算之前，我們需要知道**
s的前i - 2個字符和t的前j - 2個字符的匹配情況，這正是dp[i - 1][j - 1]**的意義。 - 即使**
s[i - 1]存在，我們也可以選擇不使用它來匹配t[j - 1]。在這種情況下，我們需要知道s的前i-2個字符和t的前j - 1個字符的匹配情況，這是dp[i - 1][j]**的意義。 - 綜合上述兩點，當**
s[i - 1]和t[j - 1]相等時，递推公式可以表示為：dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]**。
- 如果**
- if(s[i - 1] ≠ t[j - 1)
- 相當於s 要刪除元素，因為 s的字符串中，這個位置並沒有t的字串，所以要刪除
- 如果是s要刪除元素，那就是取s[i - 2] 這個不包含s[ i -1]的最大值，但t是要比較的子序列，所以t不用動，也就是說這個dp[i][j]會是由s[i - 2]t[j - 1]所組成，所對應的dp數組是dp[i][j] = dp[i - 1][j]。
- if (s[i - 1] == t[j - 1])
-
根據遞推公式、題意以及定義，確定DP數組如何初始化
dp[i][0] 一定都是1，因為把s全部刪除後出現空字符的個數就是一
dp[0][j] 因為s無論如何都無法變成t，所以都是0
dp[0][0] 空字符串s可以刪除0個元素變成空字符串t,所以等於1
-
確定遍歷順序
因為需要左上角的數據來進行遍歷，所以是由前往後。
Code
class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1, 0));
for(int i = 0 ; i <= s.size(); i++) {
dp[i][0] = 1;
}
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] + dp[i -1 ][j];
else dp[i][j] = dp[i - 1][j];
}
}
return dp[s.size()][t.size()];
}
};
總結
自己实现过程中遇到哪些困难
今天最主要的困難點在於不同的子序列，透過許多不同的方法，去釐清，後來才慢慢比較清晰了，只是這個還需要多琢磨，自己對於這部分的清晰度還需要再加強
今日收获，记录一下自己的学习时长
今天大概花了四小時，主要是去理解不同的子序列問題，在這個問題中花費了很久時間，才對題解有一些了解
相關資料
● 今日学习的文章链接和视频链接
392.判断子序列
https://programmercarl.com/0392.判断子序列.html文章来源：https://www.toymoban.com/news/detail-737687.html
115.不同的子序列
https://programmercarl.com/0115.不同的子序列.html文章来源地址https://www.toymoban.com/news/detail-737687.html
到了这里，关于代碼隨想錄算法訓練營|第五十六天|392.判断子序列、1035.不相交的线、115.不同的子序列。刷题心得（c++）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
