今天給動態規劃掃個尾，還有兩題。

第一道：647. 回文子串 - 力扣（LeetCode）

暴力解法

兩層for循環，遍歷區間起始位置和終止位置，然后還需要一層遍歷判斷這個區間是不是回文。所以時間復雜度：O(n^3)。

動態規劃

動規五部曲：

確定dp數組（dp table）以及下標的含義

本題如果定義，dp[i] 為 下標i結尾的字符串有 dp[i]個回文串的話，會發現很難找到遞歸關系。

dp[i] 和 dp[i-1] ，dp[i + 1] 看上去都沒啥關系。

在判斷字符串S是否是回文，那么如果知道 s[1]，s[2]，s[3] 這個子串是回文的，那么只需要比較 s[0]和s[4]這兩個元素是否相同，如果相同的話，這個字符串s 就是回文串。

那么此時是不是能找到一種遞歸關系，也就是判斷一個子字符串（字符串下標范圍[i,j]）是否回文，依賴于，子字符串（下標范圍[i + 1, j - 1]）） 是否是回文。

所以為了明確這種遞歸關系，dp數組要定義成一位二維dp數組。

布爾類型的dp[i][j]：表示區間范圍[i,j] （注意是左閉右閉）的子串是否是回文子串，如果是dp[i][j]為true，否則為false。

確定遞推公式

在確定遞推公式時，就要分析如下幾種情況。

整體上是兩種，就是s[i]與s[j]相等，s[i]與s[j]不相等這兩種。

當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。

以上三種情況分析完了，那么遞歸公式如下：

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;}
}

result就是統計回文子串的數量。

注意這里沒有列出當s[i]與s[j]不相等的時候，因為在下面dp[i][j]初始化的時候，就初始為false。

dp數組如何初始化

dp[i][j]可以初始化為true么？ 當然不行，怎能剛開始就全都匹配上了。

所以dp[i][j]初始化為false。

確定遍歷順序
首先從遞推公式中可以看出，情況三是根據dp[i + 1][j - 1]是否為true，在對dp[i][j]進行賦值true的。

dp[i + 1][j - 1] 在 dp[i][j]的左下角。

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

所以一定要從下到上，從左到右遍歷，這樣保證dp[i + 1][j - 1]都是經過計算的。

C++代碼如下：

class Solution {
public:int countSubstrings(string s) {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;}
};

然后看第二道：516. 最長回文子序列 - 力扣（LeetCode）

回文子串是要連續的，回文子序列可不是連續的！

動規五部曲分析如下：

確定dp數組（dp table）以及下標的含義

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]);

代碼如下：

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]);
}

dp數組如何初始化

首先要考慮當i 和j 相同的情況，從遞推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 遞推公式是計算不到 i 和j相同時候的情況。

所以需要手動初始化一下，當i與j相同，那么dp[i][j]一定是等于1的，即：一個字符的回文子序列長度就是1。

其他情況dp[i][j]初始為0就行，這樣遞推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不會被初始值覆蓋。

vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;

確定遍歷順序

從遞歸公式中，可以看出，dp[i][j] 依賴于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，

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

j的話，可以正常從左向右遍歷。

C++代碼如下：

class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));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];}
};