📝前言說明：

• 本專欄主要記錄本人的動態規劃算法學習以及LeetCode刷題記錄，按專題劃分
• 每題主要記錄：（1）本人解法 + 本人屎山代碼；（2）優質解法 + 優質代碼；（3）精益求精，更好的解法和獨特的思想（如果有的話）
• 文章中的理解僅為個人理解。如有錯誤，感謝糾錯

🎬個人簡介：努力學習ing
📋本專欄：C++刷題專欄
📋其他專欄：C語言入門基礎，python入門基礎，C++學習筆記，Linux
🎀CSDN主頁 愚潤澤

你可以點擊下方鏈接，進行不同專題的動態規劃的學習

點擊鏈接	開始學習
斐波那契數列模型	路徑問題
簡單多狀態（一）	簡單多狀態（二）
子數組系列（一）	子數組系列（二）
子序列問題（一）	子序列問題（二）
回文串問題	兩個數組dp問題（一）
兩個數組的dp問題（二）	01背包問題
完全背包	二維的背包問題
其他

---

413. 等差數列劃分

題目鏈接：https://leetcode.cn/problems/arithmetic-slices/description/

個人解

思路：

• 不解釋了，比較簡單
• 要注意的是：對于一個以i結尾的子數組，如果以起始位置沒變，改成以i + 1結尾，則這時候子數組總數 + 1

用時：12:00
屎山代碼：

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 0);for(int i = 2; i < n; i++){if(dp[i - 1] > 0 && nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])dp[i] = dp[i - 1] + 1; // else if(nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])dp[i] = 1;}int ans = 0;for(auto x: dp)ans += x;return ans;}
};

時間復雜度：O(n)
空間復雜度：O(n)

---

978. 最長湍流子數組

題目鏈接：https://leetcode.cn/problems/longest-turbulent-subarray/description/

個人解

思路：

• 麻煩點在于，要處理==的情況

用時：25:00
屎山代碼（寫的太丑陋了）：

class Solution {
public:int maxTurbulenceSize(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 1);if(n == 1) return 1;if(n == 2 && nums[1]!= nums[0]) return n;if(n == 2 && nums[1] == nums[0]) return 1;// 初始化bool flag1 = nums[1] - nums[0] > 0? true : false;bool flag2 = nums[2] - nums[1] > 0? true : false;if(nums[2] == nums[1])dp[2] = 1;else if(nums[1] == nums[0])dp[2] = 2;else dp[2] = flag1 != flag2? 3: 2;int ans = dp[2];for(int i = 3; i < n ; i++){if(nums[i] == nums[i - 1])continue;dp[i] = 2;if(nums[i - 1] == nums[i - 2])continue;flag1 = nums[i] - nums[i - 1] > 0? true : false;flag2 = nums[i - 1] - nums[i - 2] > 0? true : false;if(flag1 == flag2)continue;if(dp[i - 1] > 2)dp[i] = dp[i - 1] + 1;elsedp[i] = 3;}for(auto x: dp)ans = max(ans, x);return ans;}
};

時間復雜度：O(n)
空間復雜度：O(n)

---

優質解

• 一個湍流子數組，以i位置為結尾可以分成兩種狀態> / <
• 利用多狀態的狀態轉移來填dp

代碼（力扣官方題解）：

class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {int n = arr.size();vector<vector<int>> dp(n, vector<int>(2, 1));dp[0][0] = dp[0][1] = 1;for (int i = 1; i < n; i++) {if (arr[i - 1] > arr[i]) {dp[i][0] = dp[i - 1][1] + 1;} else if (arr[i - 1] < arr[i]) {dp[i][1] = dp[i - 1][0] + 1;}}int ret = 1;for (int i = 0; i < n; i++) {ret = max(ret, dp[i][0]);ret = max(ret, dp[i][1]);}return ret;}
};

---

139. 單詞拆分

題目鏈接：https://leetcode.cn/problems/word-break/description/

---

優質解

思路：

• dp[i]：s[0 , i]這部分子串，能否被字典中的單詞拼接而成
  • 我們怎么利用dp[i - 1]呢（前面的信息記錄的是前面的字符串能否被字典中的單詞拼接而成）
  • 也就是說：我們可以把[0, i]分成兩份，[j, i]記錄最后一個單詞（完整的）
  • 如果[j, i]的單詞在字典中，且[0, j - 1]這部分能被字典拼接而成，則i位置就行。巧妙用到的dp[j]
• 狀態轉移方程：j遍歷[0, i]（即得到i結尾的最后一個單詞）
  • 如果，dp[j - 1] == true && s[j, i] in wordDict：true
  • 否則，false
• 初始化：j會越界，添加一個哨兵節點。那此時字符串的下標和數組不對應了，所以我們可以在字符串前面也加多一個字符串。且dp[0] = true
• 填表順序：從左往右
• 返回值：dp[n]

代碼：

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordDictset; // 轉換成哈希表，后續使用find方便for(auto word:wordDict){wordDictset.insert(word);}s = '0' + s;int n = s.size();vector<bool> dp(n + 1, false);dp[0] = true;for(int i = 1; i <= n; i++){for(int j = i; j >= 1; j--) // 選擇從后往前{if(dp[j - 1] && wordDictset.find(s.substr(j, i - j + 1)) != wordDictset.end()){dp[i] = true;break;}}}return dp[n];}
};

---

467. 環繞字符串中唯一的子字符串

題目鏈接：https://leetcode.cn/problems/unique-substrings-in-wraparound-string/description/

個人解

思路：

• dp[i]：以 i 結尾的子串是否在 base 中出現
• 狀態轉移：如果dp[i - 1] > 1 && (s[i] == s[i - 1] + 1 || s[i] == s[i - 1] - 25) // 回繞到 z
  • 則 dp[i] = dp[i - 1] + 1
• 重復子串怎么處理呢？？？

---

優質解

思路：

• 對于這種子串問題，我們可以以最后一個位置為結尾，把子串的狀態專業給區分出來，如：單獨最后一個位置 / 前 i - 1的子串 + 最后一個位置
• 返回值是重難點
• 對于重復的子串，長的子串一定包含短的子串的所有子串
• 所以，我們可以遍歷dp表，對于相同的字符的dp值，只添加大的

代碼：

class Solution {
public:int findSubstringInWraproundString(string s) {int n = s.size();int dp_max[26] = {0}; // 記錄每個字符出現的子串的最大值vector<int> dp(n, 1); // 單個字符，dp[i] == 1dp_max[s[0] - 'a'] = 1;for(int i = 1; i < n; i++){if(s[i] == s[i - 1] + 1 || s[i] == s[i - 1] - 25)dp[i] += dp[i - 1];dp_max[s[i] - 'a'] = max(dp_max[s[i] - 'a'], dp[i]); // 更新字符對應的子串最大值}int ans = 0;for(auto x: dp_max)ans += x;return ans;}
};

時間復雜度：O(n)
空間復雜度：O(n)

---

🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助，那簡直是太酷啦！
若有不足，還請大家多多指正，我們一起學習交流！
📢公主，王子：點贊👍→收藏?→關注🔍
感謝大家的觀看和支持！祝大家都能得償所愿，天天開心！！！