?📝個人主頁：@Sherry的成長之路
🏠學習社區(qū)：Sherry的成長之路（個人社區(qū)）
📖專欄鏈接：練題
🎯長路漫漫浩浩，萬事皆有期待

回文子串

647. 回文子串 - 力扣（LeetCode）

給一個字符串 s ，請你統(tǒng)計并返回這個字符串中 回文子串 的數(shù)目?；匚淖址?是正著讀和倒過來讀一樣的字符串。

子字符串 是字符串中的由連續(xù)字符組成的一個序列。

具有不同開始位置或結(jié)束位置的子串，即使是由相同的字符組成，也會被視作不同的子串。

1. 確定dp數(shù)組（dp table）以及下標的含義
   dp[i] 和 dp[i-1] ，dp[i + 1] 看上去都沒啥關(guān)系。

所以我們要看回文串的性質(zhì)。

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

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

所以為了明確這種遞歸關(guān)系，我們的dp數(shù)組是要定義成一位二維dp數(shù)組。

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

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

整體上是兩種，就是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]已經(jīng)相同了，我們看i到j區(qū)間是不是回文子串就看aba是不是回文就可以了，那么aba的區(qū)間就是 i+1 與 j-1區(qū)間，這個區(qū)間是不是回文就看dp[i + 1][j - 1]是否為true。

3. dp數(shù)組如何初始化
   dp[i][j]初始化為false。

4. 確定遍歷順序
   遍歷順序可有有點講究了。

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

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

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

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

有的代碼實現(xiàn)是優(yōu)先遍歷列，然后遍歷行，其實也是一個道理，都是為了保證dp[i + 1][j - 1]都是經(jīng)過計算的。

5. 舉例推導dp數(shù)組
   舉例，輸入：“aaa”，dp[i][j]狀態(tài)如下：
   

圖中有6個true，所以就是有6個回文子串。

class Solution {public int countSubstrings(String s) {boolean[][] dp = new boolean[s.length()][s.length()];for (boolean[] a: dp) {Arrays.fill(a,false);}int result = 0;for (int i = s.length()-1; i>=0 ; i--) {for (int j = i; j <s.length() ; j++) {if (s.charAt(i)==(s.charAt(j))) {if (j-i<=1){dp[i][j] = true;result++;}else if(dp[i+1][j-1]==true){dp[i][j] = true;result++;}}}}return result;}
}

最長回文子序列

516. 最長回文子序列 - 力扣（LeetCode）

給一個字符串 s ，找出其中最長的回文子序列，并返回該序列的長度。
子序列定義為：不改變剩余字符順序的情況下，刪除某些字符或者不刪除任何字符形成的一個序列。

動規(guī)五部曲分析如下：

1. 確定dp數(shù)組（dp table）以及下標的含義
   dp[i][j]：字符串s在[i, j]范圍內(nèi)最長的回文子序列的長度為dp[i][j]。

2. 確定遞推公式
   在判斷回文子串的題目中，關(guān)鍵邏輯就是看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]區(qū)間回文子序列的長度，那么分別加入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]);

3. dp數(shù)組如何初始化
   首先要考慮當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]才不會被初始值覆蓋。

4. 確定遍歷順序
   從遞歸公式中，可以看出，dp[i][j] 依賴于 dp[i + 1][j - 1] ，dp[i + 1][j]和 dp[i][j - 1]

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

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

5. 舉例推導dp數(shù)組

輸入s:“cbbd” 為例，dp數(shù)組狀態(tài)如圖：

紅色框即：dp[0][s.size() - 1]; 為最終結(jié)果。

class Solution {public int longestPalindromeSubseq(String s) {int[][] dp = new int[s.length()][s.length()];for (int i = 0; i <s.length(); i++) {dp[i][i] = 1;}for (int i = s.length()-1; i >=0 ; i--) {for (int j =i+1; j <s.length(); j++) {if (s.charAt(i)==s.charAt(j)) dp[i][j]=dp[i+1][j-1]+2;else dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j]);}}return dp[0][s.length()-1];}
}

總結(jié)：

今天我們完成了回文子串、最長回文子序列兩道題，相關(guān)的思想需要多復習回顧。接下來，我們繼續(xù)進行算法練習。希望我的文章和講解能對大家的學習提供一些幫助。

當然，本文仍有許多不足之處，歡迎各位小伙伴們隨時私信交流、批評指正！我們下期見~