题面:
解题思路:
本题是一个经典的动态规划的题目。定义动态规划数组dp,dp[i]的含义是子串str[0…i]至少需要切割几次,才能把str[0…i]全部切成回文子串。那么dp[len-1]就是最后的结果。
从左往右依次计算dp[i]的值,i 初始为0,具体计算过程如下:
1、假设 j 处在 0 到 i 之间,如果str[j…i]是回文串,那么dp[i]的值可能是dp[j-1] + 1,其含义是在str[0…i]上,既然str[j…i]是回文串,那么它可以自己作为一个分割的部分,剩下的部分str[0…j-1]继续做最经济的分割,也就是dp[j-1]的值。
2、根据步骤1的方式,让 j 在 i 到 0 的位置上枚举,那么所有可能中最小值就是dp[i]的值,即dp[i] = min{dp[j-1]+1 (0<= j <= i,且str[j…i]必须是回文串)}。
状态转移方程
if( i 到 j 是回文串 )
dp [ i ] = min ( dp[ i ] , dp[ j-1 ] + 1)
代码:
#include <iostream> #include <memory.h> #include <string> using namespace std; string s; int dp[1005]; int check(int left, int right) { int mid = (left + right ) / 2; for( int i = left; i <= mid; i++ ) if( s[i] != s[right + left - i] ) return false; return true; } int main() { cin >> s; memset(dp, 0, sizeof(dp)); int len = s.size(); for( int i = 2; i <= len; i++ ) dp[i] = (1<<30); dp[0] = -1;dp[1] = 0; for( int i = 2; i <= len; i++ ) for( int j = 1; j <= i; j++ ) { if( check(j-1,i-1) ) dp[i] = min(dp[i], dp[j-1] + 1); } cout << dp[len] << endl; return 0; }
标签:切割,int,HZOJ,str,left,include,dp,回文 From: https://www.cnblogs.com/anaxiansen/p/17016334.html