回文子串、回文子序列相關題目

dp數組含義：$dp[i][j]$ 表示子序列 $s[i,j]$ 中的最長回文子序列的長度。

dp數組初始化：子序列長度為 1 時，最長回文子序列的長度就是 1， 即$s[i,i]=1$

遞推公式：

• 如果 $s[i]==s[j]$ ，那么相比于 $s[i+1,j?1]$ ，$s[i,j]$ 的最長子序列的長度增加了 2（首尾）
• 如果 $s[i]=s[j]$，那么 $s[i,j]$ 的最長子序列的長度就是 $s[i+1,j],s[i,j?1]$ 中的較大者（取首或者取尾）

遍歷順序：

這里順序比較講究，我們知道，動態規劃解法的遍歷順序需要遵循的原則是要按照遞推公式的依賴關系，即遞推公式中計算 dp 數組中的某個值時一定要保證它所依賴的值已經在 dp 數組中被計算好了。

在本題中，我們看到遞推公式中，$dp[i][j]$ 的值依賴于三個值：$dp[i+1][j?1]$ 、$dp[i+1][j]$、$dp[i][j?1]$，我們所選擇的遍歷順序需要保證在計算 $dp[i][j]$ 時這三個值都已經計算過了，那么很明顯的，$i$ 要從大往小，$j$ 要從小往大。

class Solution {
public:int longestPalindromeSubseq(string s) {int n = s.size();vector<vector<int>> dp(n, vector<int> (n));for (int i=0; i<n; ++i) dp[i][i] = 1;for (int i=n-1; i>=0; --i) {for (int j=i+1; j<n; ++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][n-1];}
};

dp數組含義：$dp[i][j]$ 表示子串 $s[i,j]$ 是否為回文串。

dp數組初始化：長度為 1 的子串，即 $s[i,i]$ 一定是回文串。

遞推公式：

• 如果 $s[i]=s[j]$，那么 $s[i,j]$ 一定不是回文串；
• 如果 $s[i]==s[j]$， 那要再看子串的長度：
  • 如果子串長度小于等于 3， 那 $s[i,j]$ 一定是回文串
  • 如果子串長度大于 3，則 $s[i,j]$ 是不是回文串就取決于 $s[i+1][j?1]$ 是不是回文串。如 sabas 是不是回文串取決于 aba 是不是回文串。

遍歷順序：

外層循環遍歷子串的長度，內層循環遍歷起始位置，這里也可以考慮與上面類似的遍歷順序思路，會在下一題中給出代碼。

class Solution {
public:string longestPalindrome(string s) {int n = s.size();if (n < 2) return s;string ans(1, s[0]);vector<vector<bool>> dp(n, vector<bool> (n));for (int i=0; i<n; ++i) dp[i][i] = true;for (int len=2; len<=n; ++len) {for (int i=0; i<n; ++i) {int j = i + len - 1;if (j >= n) break;if (s[i] != s[j]) dp[i][j] = false;else {if (len <= 3) dp[i][j] = true;else dp[i][j] = dp[i+1][j-1];}if (dp[i][j] && len>ans.size()) ans = s.substr(i, len);}}return ans;}
};

思路和上一題邏輯類似

遍歷順序一，與上題一致

class Solution {
public:int countSubstrings(string s) {int n = s.size();if (n < 2) return n;vector<vector<bool>> dp(n, vector<bool> (n));for (int i=0; i<n; ++i) dp[i][i] = true;int ans = n;for (int len=2; len<=n; ++len) {for (int i=0; i<n; ++i) {int j = i + len - 1;if (j >= n) break;if (s[i] != s[j]) dp[i][j] = false;else {if (len <= 3) {dp[i][j] = true;++ans;}else {if (dp[i+1][j-1]) {dp[i][j] = true;++ans;}else dp[i][j] = false;}}}}return ans;}
};

另一種根據長度和起始位置的遍歷順序，思路類似題516：

class Solution {
public:int countSubstrings(string s) {int n = s.size();int ans = 0;vector<vector<bool>> dp(n, vector<bool> (n, false));for (int i=n-1; i>=0; --i) {for (int j=i; j<n; ++j) {if (s[i] == s[j]) {if (abs(i-j) <= 1) {dp[i][j] = true;++ans;}else {if (dp[i+1][j-1]) {dp[i][j] = true;++ans;}}}}}return ans;}
};