動態規劃
題目
1143. 最長公共子序列 - 力扣（LeetCode）
公共子序列，類似于最長重復子數組，但是不要求連續 (子序列)
1. 定義 dp，dp[i][j] 表示以 i-1 與 j-1 結尾的最長公共子序列的長度
2. 定義遞推公式
如果字符相同，則在基礎上+1
if (text1[i-1] == text2[i-1]) dp[i][j] = dp[i-1][j-1] +1
如果字符不同，分別屏蔽 i-1 和 j-1 對比字符
else dp[i][j] = std::max(dp[i][j-1], dp[i-1][j])
3. 初始化 dp，由于 dp 是從前往后推導，且定義為 i-1, j-1
其中 0-1 時候結果為 0 意思是字符串與空字符查找那最大的公共子序列結果為 0
4. 遍歷順序是從前往后，從上到下遍歷
5. 打印 dp
int longestCommonSubsequence(string text1, string text2) {// 定義dp數組std::vector<std::vector<int>> dp(text1.size()+1, std::vector<int>(text2.size()+1, 0));// 遍歷dp數組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] = std::max(dp[i-1][j], dp[i][j-1]);}}return dp[text1.size()][text2.size()];
}
1035. 不相交的線 - 力扣（LeetCode）
本題說是求繪制的最大連線數，其實就是求兩個字符串的最長公共子序列的長度！
1. 定義 dp，dp[i][j] 表示以 i-1 j-1 結尾的最長公共子序列長度
2. 遞推公式類上題
3. 初始化類似上題
4. 遍歷順序同上題
5. 打印 dp
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {// 定義dp數組 i-1 j-1 結尾之前最大的公共子序列std::vector<std::vector<int>> dp(nums1.size()+1, std::vector<int>(nums2.size()+1, 0));// forfor (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;else dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);}}return dp[nums1.size()][nums2.size()];
}
53. 最大子數組和 - 力扣（LeetCode）
之前貪心做過 [[Day27 貪心Ⅰ 分餅干 擺動序列 最大子序列和#題目]]，貪心就是小于 0不取
使用 dp 再做一遍，整體類似于基本的 dp 如打家劫舍、股票
1. 定義 dp，dp[i] 表示 i 之前的最大連續子數組和
2. 遞推公式：基于之前的結果與當前結果的最大值作為當前 i 的 dp 值
dp[i] = max(dp[i-1]+nums[i], nums[i])
3. 初始化由于都是從前面推導的，因此 dp[0] = nums[0]
最大和要尋找 dp 最大值，使用 res 比較獲取
4. 遍歷順序從前往后
5. 打印 dp
int maxSubArray(vector<int>& nums) {// 定義dp數組std::vector<int> dp(nums.size(), 0);// 初始化dp res也定義為nums[0]值保不忽略第一個元素dp[0] = nums[0];int res = nums[0];// 遍歷dpfor (int i = 1; i < nums.size(); ++i) {dp[i] = std::max(dp[i-1] + nums[i], nums[i]);if (dp[i] > res) res = dp[i];}return res;
}
392. 判斷子序列 - 力扣（LeetCode）
編輯距離問題，本體的本質就是求 s 與 t 的最長公共子序列，只不過這個 s 不可刪除
1. dp[i][j] 表示 i-1, j-1 為結尾的 s/t 字符串的最長公共子序列的長度
2. 遞推公式類似求最長公共子序列固定 s 不變，只刪除 t（dp[i][j-1]）
if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1]+1
else dp[i][j] = dp[i][j-1]
3. 初始化 dp 數組
因為定義為 i-1,j-1 因此初始化為 0 即可，之后使用遞推公式就可以推出
4. 遍歷順序從前往后遍歷，結果與 s 相等說明可以匹配
5. 打印 dp
bool isSubsequence(string s, string t) {// 定義dpstd::vector<std::vector<int>> dp(s.size()+1, std::vector<int>(t.size()+1, 0));// 遍歷dpfor (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]; // t 刪除 匹配s}}if (dp[s.size()][t.size()] == s.size()) return true;else return false;
}
