1. 回文子串

状态表示:dp[i][j]: 表示以i位置开始，j位置结尾的子串是否是回文串
状态转移方程:i == j: dp[i][j] = true;i + 1 == j && s[i] == s[j]: dp[i][j] = true;i + 1 < j && dp[i+1][j-1] && s[i] == s[j]: dp[i][j] = true;

int countSubstrings(string s)
{// 1.dp数组vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));// 2.初始化// 3.状态转移方程for(int i = s.size() - 1; i >= 0; --i){for(int j = i; j < s.size(); ++j){if(i == j){dp[i][j] = true;}else if(i + 1 == j){if(s[i] == s[j]) dp[i][j] = true;}else{if(dp[i+1][j-1] && s[i] == s[j]) dp[i][j] = true;}}}// 4.返回值int ret = 0;for(int i = s.size() - 1; i >= 0; --i){for(int j = i; j < s.size(); ++j){ret += dp[i][j];}}return ret;
}

2. 最长回文子串

状态表示:dp[i][j]: 表示以i位置开始，j位置结尾的子串是否是回文串
状态转移方程:i == j: dp[i][j] = true;i + 1 == j && s[i] == s[j]: dp[i][j] = true;i + 1 < j && dp[i+1][j-1] && s[i] == s[j]: dp[i][j] = true;

string longestPalindrome(string s) 
{// 1.dp数组vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));// 2.初始化// 3.状态转移方程for(int i = s.size() - 1; i >= 0; --i){for(int j = i; j < s.size(); ++j){if(i == j){dp[i][j] = true;}else if(i + 1 == j){if(s[i] == s[j]) dp[i][j] = true;}else{if(dp[i+1][j-1] && s[i] == s[j]) dp[i][j] = true;}}}// 4.返回值int start = -1, end = -1;for(int i = s.size() - 1; i >= 0; --i){for(int j = i; j < s.size(); ++j){if(dp[i][j] == true){if(start == -1){start = i;end = j;}else{if(j - i > end - start){start = i;end = j;}}}}}return s.substr(start, end - start + 1);
}

3. 分割回文串 IV

状态表示:dp[i][j]: 表示以i位置开始，j位置结尾的子串是否是回文串
状态转移方程:i == j: dp[i][j] = true;i + 1 == j && s[i] == s[j]: dp[i][j] = true;i + 1 < j && dp[i+1][j-1] && s[i] == s[j]: dp[i][j] = true;

bool checkPartitioning(string s)
{// 1.dp数组vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));// 2.初始化// 3.状态转移方程for(int i = s.size() - 1; i >= 0; --i){for(int j = i; j < s.size(); ++j){if(i == j) dp[i][j] = true;else if(i + 1 == j && s[i] == s[j]) dp[i][j] = true;else if(dp[i+1][j-1] && s[i] == s[j]) dp[i][j] = true;}}// 4.返回值for(int i = 1; i < s.size() - 1; ++i){for(int j = i; j < s.size() - 1; ++j){if(dp[0][i-1] && dp[i][j] && dp[j+1][s.size() - 1]) return true;}}return false;
}

4. 分割回文串 II

状态表示:dp[i]: 表示 s[0, i]这个子串区间，最少的分割次数
状态转移方程:dp[i] = min(dp[j-1]+1)

int minCut(string s)
{// 0.优化vector<vector<bool>> vv(s.size(), vector<bool>(s.size(), false));for(int i = s.size() - 1; i >= 0; --i){for(int j = i; j < s.size(); ++j){if(i == j) vv[i][j] = true;else if(i + 1 == j && s[i] == s[j]) vv[i][j] = true;else if(vv[i+1][j-1] && s[i] == s[j]) vv[i][j] = true;}}// 1.dp数组vector<int> dp(s.size());// 2.初始化// 3.状态转移方程for(int i = 0; i < dp.size(); ++i){if(vv[0][i]) dp[i] = 0;else{int m = INT_MAX;for(int j = i; j > 0; --j){if(vv[j][i]) m = min(m, dp[j-1] + 1);}dp[i] = m;}}// 4.返回值return dp.back();
}

5. 最长回文子序列

状态表示:dp[i][j]: 表示s字符串[i,j]区间内的所有子序列中，最长回文子序列的长度
状态转移方程:s[i] == s[j]:if(i == j) dp[i][j] = 1;else if(i + 1 == j) dp[i][j] = 2;else dp[i][j] = dp[i+1][j-1] + 2;s[i] != s[j]:dp[i][j] = max(dp[i+1][j], dp[i][j-1]);

int longestPalindromeSubseq(string s)
{// 1.dp数组vector<vector<int>> dp(s.size(), vector<int>(s.size()));// 2.初始化// 3.状态转移方程for(int i = s.size() - 1; i >= 0; --i){for(int j = i; j < s.size(); ++j){if(s[i] == s[j]){if(i == j) dp[i][j] = 1;else if(i + 1 == j) dp[i][j] = 2;else dp[i][j] = dp[i+1][j-1] + 2;}else{dp[i][j] = max(dp[i+1][j], dp[i][j-1]);}}}// 4.返回值return dp[0][s.size() - 1];
}

6. 让字符串成为回文串的最少插入次数

状态表示:dp[i][j]: 表示s字符串中[i,j]区间的子串，成为回文串的最小插入次数
状态转移方程:s[i] == s[j]:if(i == j || i + 1 == j) dp[i][j] = 0;else dp[i][j] = dp[i+1][j-1];s[i] != s[j]:dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;

int minInsertions(string s)
{// 1.dp数组vector<vector<int>> dp(s.size(), vector<int>(s.size()));// 2.初始化// 3.状态转移方程for(int i = s.size(); i >= 0; --i){for(int j = i; j < s.size(); ++j){if(s[i] == s[j]){if(i == j || i + 1 == j) dp[i][j] = 0;else dp[i][j] = dp[i+1][j-1];}else{dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;}}}// 4.状态转移方程return dp[0][s.size() - 1];
}