动态规划基础题2

切割回文串

演示代码 C++

问题描述： 给定一个字符串，求最少切几次，可以都切成回文串 例如： 对于字符串“abaacca”，最少切割一次，就可以得到“aba”和“acca”这两个回文子串 输入 输入的第一行是一个整数 T (T <= 20) ，表示一共有 T 组数据。 接下来的 T 行，每一行都包含了一个长度不超过的 1000 的字符串，且字符串只包含了小写字母。 输出 对于每组数据，输出一行。该行包含一个整数，表示阿福最少切割的次数，使得切割完得到的子串都是回文的。 样例输入 3 abaacca abcd abcba 样例输出 1 3 0 提示 对于第一组样例，最少切割 1 次，将原串切割为“aba”和“acca”两个回文子串。 对于第二组样例，最少切割 3 次，将原串切割为“a”、“b”、“c”、“d”这四个回文子串。 对于第三组样例，不需要切割，原串本身就是一个回文串。

思路

首先写好判断回文串的函数 dp[i]表示 从1到i 完全形成回文串需要切几刀 从1为起点开始枚举 出口 dp[0],dp[1]求dp[len] 相当于斜着遍历 如果i到j是回文串 从1到j 也就是i == 1时 需要切一刀2.需要综合之前其他起点的情况 也就是dp[i] = min(dp[i],dp[j-1]);

题解

#include<iostream> #include<algorithm> #include<cstring> using namespace std; char a[100]; int dp[100]; bool check(int left, int right){ int mid = (left + right ) / 2; for( int i = left; i <= mid; i++ ) if( a[i] != a[right + left - i] ) return false; return true; } int main(){ cin >>a+1; int len = strlen(a+1); dp[0] = -1; dp[1] = 0; for(int i = 2;i<=len;i++){ dp[i] = 1; } for(int i = 2;i<=len;i++){ dp[i] = 55; for(int j = 1;j<=i;j++){ if(check(j,i)){ dp[i] = min(dp[i],dp[j-1]+1); } } } cout <<dp[len]<<endl; return 0; }