本文主要是介绍LIGHTOJ 1044（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给你一个字符串，让你找出回文串的最少个数
题解：查询当前字符与前面字符子串是否构成回文串，如果构成则 dp[i] = min(dp[i],dp[j-1]+1);
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[1005];
char str[1005];
bool find(int k,int r)
{while(k < r){if(str[k] == str[r]) k++,r--;else return false;}return true;
}
int main()
{int n,Case = 1;;scanf("%d",&n);getchar();while(n--){scanf("%s",str);int l = strlen(str);for(int i = 0; i < l; i++){dp[i] = i + 1;for(int j = 0; j <= i; j++){if(find(j,i)){if(j == 0)dp[i] = 1;elsedp[i] = min(dp[i],dp[j - 1] + 1);}}}printf("Case %d: %d\n",Case++,dp[l-1]);}
}
这篇关于LIGHTOJ 1044（动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
