问题一：求一个字符串的最大回文字符串长度;
1）思路：动态规划;
2）具体描述：设立一个长度len为字符串str，用一个dp[len][len]的二维数组来表示字符串i-j下标所构成的子串的长度，经过循环计算之后我们返回最大回文子串的长度即可，即返回dp[0][len-1];
3）dp数组的具体实现：根据动态规划自底向上的思想，从回文子串到求出整个最长回文字符串，首先从str的结尾开始遍历到str 的头部，同时每一次记录dp的初始值；如果str[i]==str[j],说明i-j为回文字符串，此时应该更新dp[i][j]的值；如果str[i]≠str[j]，应该判断dp[i+1][j]和dp[i][j-1]的大小，取出其中max作为最大长度更新dp[i][j]的值
static int longestPalindrome1(String str) {
int len = str.length();
for (int i = len - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i+1; j < len; j++) {
if(str[i] == str[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][len-1];
}
还有一个题用了两个dp：
https://leetcode-cn.com/problems/palindrome-partitioning-ii/submissions/
这个题用dfs一直t，估计是要用动态规划：
class Solution {
public:
vector<vector<int>> f;
int n;
int minx=1000000;
int minCut(string s) {
n=s.length();
f.assign(n,vector<int>(n,true));
for(int i=n-1;i>=0;i--){
for(int j=i+1;j<n;j++){
f[i][j]=(s[i]==s[j]&&f[i+1][j-1]);
}
}
vector<int> dp(s.size() + 1, 0);
for (int i = 0; i < s.size(); i++) dp[i] = i;
for (int i = 1; i < s.size(); i++) {
if (f[0][i]) {
dp[i] = 0;
continue;
}
for (int j = 0; j < i; j++) {
if (f[j + 1][i]) {
dp[i] = min(dp[i], dp[j] + 1);
}
}
}
return dp[s.size() - 1];
}
};