题意:输入一个由小写字母组成的字符串,要求把它划分成尽量少的回文串。输出最少的个数。

dp[i]dp[i]表示前i个划分成的最少回文串那么dp[i]=min(dp[j])+1dp[i] = min(dp[j]) + 1 满足[j+1,i][j + 1, i] 为一个回文串

对于某个区间是否为回文串可以用一个记忆化搜索来实现。

   #include <bits/stdc++.h>
   #define pa pair<int, int>
   #define mp make_pair
   #define lowbit(x) ((x)&(-x))
   #define mem(i, a) memset(i, a, sizeof(i))
   using namespace std;
   typedef long long ll;
   const int INF = 0x3f3f3f3f;
   const int MAXN = 1005 + 5;
   char s[MAXN];
   int vis[MAXN][MAXN];
   int f[MAXN];
   int n;
   bool is_partition(int i, int j) {
       if(i >= j) return 1;
       if(s[i] != s[j]) return 0;
       if(vis[i][j]) return 1;
       vis[i][j] = is_partition(i + 1, j - 1);
       return vis[i][j];
   }
   int main() {
       int t;
       cin >> t;
       while(t--) {
           scanf("%s", s + 1);
           n = strlen(s + 1);
           mem(vis, 0); 
           for(int i = 1; i <= n; i++) {
               f[i] = i;
               for(int j = 0; j < i; j++) 
                   if(is_partition(j + 1, i)) f[i] = min(f[j] + 1, f[i]);
           }
           cout << f[n] << '\n';
       }
       return 0;
   }
   ```