? ? ? ? 大家好，首先感慨一下，時間過的真是快，不知不覺我們的訓練營就已經到第五十天了，首先祝賀自己一直在堅持，今天是我們動態規劃章節的收官之戰，明天我們就會走進一個全新的算法章節單調棧，我們要為我們的動態規劃章節畫上一個完美的句號，那我們就開始我們今天的動態規劃的題目。

第一題對應力扣編號為647的題目回文子串

? ? ? ? 其實大家應該很熟悉什么叫回文子串了，就是倒著讀和正著讀是一樣的，當然很明顯一個字符的字符串當然是回文串，那今天的這道題目是什么意思呢？我們先一起來看一下：

? ? ? ? 其實很明顯題目是要求我們去求回文串的個數，我們就直接考慮使用動態規劃的思路來解決這道題目，當然免不了要使用動規五部曲：

? ? ? ? 第一步確定dp數組以及下標的含義：這道題目就有點不一樣了，我們以前做過的絕大部分題目我們都是題目要求什么我們就定義什么，但是在這里我們如果還要定義dp[i] 為 下標i結尾的字符串有 dp[i]個回文串的話我們就會發現我們壓根找不到遞推關系，這樣就不好了，沒有遞推關系我們可怎么解決這道題目？大家其實想想我們回文串dp[i]與dp[i-1]與dp[i+1]是否存在什么關系嗎？好像是沒有的，它們壓根可以表示任意一個字符，而且還有回文串的長度也是不確定的，因此我們這時候去看回文串的關系示意圖：

? ? ? ? 我們的確使用一個變量跟本表示不了回文字符串，因此我們就需要考慮使用類似于雙指針的思想，其實我們在寫判斷回文字符串的函數的時候我們也是會考慮使用雙指針的思想來判斷，因此我們可以這樣判斷回文串了，因此我們就可以找到合適的定義dp數組的方法，我們就可以這樣定義：布爾類型的dp[i][j]：表示區間范圍[i,j] （注意是左閉右閉）的子串是否是回文子串，如果是dp[i][j]為true，否則為false。

? ? ? ?第二步確定遞推公式，在確定遞推公式時，就要分析如下幾種情況。其實主要是兩種情況，第一種情況當s[i]與s[j]不相等，那沒啥好說的了，dp[i][j]一定是false。也就說明我們當前的字符串一定不是回文字符串，第二種情況大家需要仔細考慮就是s[i]與s[j]相等，首先第一種可能是下標i 與 j相同，同一個字符例如a，當然是回文子串，第二種可能是下標i 與 j相差為1，例如aa，也是回文子串，i 與 j相差大于1的時候，例如cabac，此時s[i]與s[j]已經相同了，我們看i到j區間是不是回文子串就看aba是不是回文就可以了，那么aba的區間就是 i+1 與 j-1區間，這個區間是不是回文就看dp[i + 1][j - 1]是否為true。以上所有的情況都必不可少。

? ? ? 第三步就是初始化dp數組，dp[i][j]可以初始化為true么？ 當然不行，怎能剛開始就全都匹配上了。因此我們需要把dp[i][j] = false才可以。

? ? ? 第四步確定遍歷順序，這個有點意思，我們還是得看一下dp數組的示意圖：

? ? ? ? 因此我們如果這矩陣是從上到下，從左到右遍歷，那么會用到沒有計算過的dp[i + 1][j - 1]，也就是根據不確定是不是回文的區間[i+1,j-1]，來判斷了[i,j]是不是回文，那結果一定是不對的。我們需要一定要從下到上，從左到右遍歷，這樣保證dp[i + 1][j - 1]都是經過計算的。

? ? ? ? 經過上述分析，我們就可以給出本題的解題代碼：

class Solution {
public:int countSubstrings(string s) {//初始化dp數組vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));//存儲回文字串的個數int result = 0;//遍歷順序for (int i = s.size() - 1; i >= 0; --i){for (int j = i; j < s.size(); ++j){if (s[i] == s[j]){if (j - i <= 1) result++, dp[i][j] = true;else if (dp[i + 1][j - 1]) result++, dp[i][j] = true;}}}return result;}
};

? ? ? ? 這道題其實有點反常規操作，當然理解遍歷順序與定義dp數組的思想是關鍵，我們這道題就分享到這里，我們繼續我們的下一道題目。

第二題對應力扣編號為516的題目最長的回文子序列

? ? ? ?這道題與上一道題目應該是類似的，還是回文子串的問題，我們先看一下題目要求：

? ? ? ? 我們應該是返回最長的回文子序列的長度，而且其實我們是可以對原字符串進行刪除操作的，其實就是告訴我們我們找到的回文字符串未必是連續的，我們就使用動規五部曲來解決這道題目：

? ? ? 第一步確定dp數組以及下標的含義，dp[i][j]：字符串s在[i, j]范圍內最長的回文子序列的長度為dp[i][j]。

? ? ? 第二步是確定遞推公式，在判斷回文子串的題目中，關鍵邏輯就是看s[i]與s[j]是否相同。如果s[i]與s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;這個很明顯，如果s[i]與s[j]不相同，說明s[i]和s[j]的同時加入 并不能增加[i,j]區間回文子序列的長度，那么分別加入s[i]、s[j]看看哪一個可以組成最長的回文子序列。這個理解起來有點難度，大家應該記得上一道題目的思路，加入s[j]的回文子序列長度為dp[i + 1][j]，加入s[i]的回文子序列長度為dp[i][j - 1]。那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])，其實我們還是進行了刪除操作，感覺與前面的題目思路都有相似的地方，理解dp數組的含義很重要。

? ? ? 第三步是初始化dp數組，首先要考慮當i 和j 相同的情況，從遞推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 遞推公式是計算不到 i 和j相同時候的情況。其實我們需要考慮的是當i與j相同，那么dp[i][j]一定是等于1的，其他情況dp[i][j]初始為0就行，這樣遞推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不會被初始值覆蓋。

? ? ? 第四步就是確定遍歷順序，大家看下面的圖：?

? ? ? ?我們就可以理解，所以遍歷i的時候一定要從下到上遍歷，這樣才能保證下一行的數據是經過計算的。

? ? ?綜合上述分析我們就可以給出答案：

class Solution {
public:int longestPalindromeSubseq(string s) {//定義dp數組vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));//dp數組的初始化for (int i = 0; i < s.size(); ++i) dp[i][i] = 1;//確定遍歷順序for (int i = s.size() - 1; i >= 0; --i){for (int j = i + 1; j < s.size(); ++j){if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;else dp[i][j] = max(dp[i + 1][j],dp[i][j - 1]);}}return dp[0][s.size() - 1];}
};

動態規劃總結篇

? ? ? ? 到這里我們就完成了動態規劃的所有題目，其實動態規劃的題目類型很多，我們刷了不少類型，我們也深刻理解了動規五部曲在解題中的巧妙使用，如果遇到問題大家可以這樣想：我們如果想不清楚dp數組的具體含義，遞歸公式從何談起，甚至初始化的時候就寫錯了。如果看過背包系列，特別是完全背包，那么兩層for循環先后順序絕對可以搞懵很多人，反而遞歸公式是簡單的。背包問題要注意區分，我們的遍歷順序很重要，希望大家可以好好努力，多去理解，掌握任何一種算法都不簡單，更何況是動態規劃這種比較難的題目，我們今天的分享就到這里，我們明天的單調棧見！