题目： 求出字符串中回文串序列数最小是多少。UAV11584 思路很简单，状态d(i)表示成前i个子串中的回文序列数目的最小值，那么状态转移方程为d(i)=min(d(i),d(j)+1)（当str(i,j)为回文串时），注意对d(i)的初始化，然后每次判断str(j+1,i),因为d(j)（也就是j以前的最小串的数值）我已经知道了。动态规划的问题，在确定好状态之后，可以举个小例子按照定义的状态模拟一遍状态转换的思路，才不会出现问题。 AC代码：
// UVA11584.cpp : 定义控制台应用程序的入口点。 // #include <iostream> #include <string.h> #include <algorithm> #define INF 1000000 using namespace std; const int maxn = 1005; int d[maxn]; char str[maxn]; //两头向中间搜，判断回文串 //偶数时length最后=0，奇数时最后等于1,能够递归到最后就说明是回文数 int IsPalindrome(int low, int high, char *str, int length) { if (length == 0 || length == 1) return 1; if (str[low] != str[high]) return 0; return IsPalindrome(low + 1, high - 1, str, length - 2); } int main() { int num = 0; string str_temp; cin >> num; for (int i = 0; i < num; i++) { memset(str, 0, sizeof(str)); memset(d, INF, sizeof(d)); cin >> str; int len = strlen(str); bool flag = false; for (int i = 0; i < len;i++) if (IsPalindrome(0, i, str, i + 1))d[i] = 1; for (int i = 0; i < len; i++) for (int j = 0; j <= i; j++) { if (IsPalindrome(j + 1, i, str, i - j)) d[i] = min(d[i], d[j] + 1); } cout << d[len - 1] << endl; } return 0; }