首页 > 代码库 > UVA 11584 DP
UVA 11584 DP
UVA的OJ登不上去, 所以只能简述一下题意。。。。
题目大意:
输入一个字符串, 求该字符串最少能够划分成几个回文串?
解题思路:
这道题是刘汝佳紫书上的一道题, dp专题, 首先写一个判断是不是回文串的函数, dp转移方程是dp[i] = min{ i+1, dp[j-1]+1(j~i为回文串) }。
题目代码:
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; char a[100]; int dp[100]; bool isPalind( int j, int i ) { while( j < i ) { if( a[j] != a[i] ) return false; j++; i--; } return true; } int main() { scanf( "%s", a ); int len = (int)strlen( a ); for( int i = 0; i < len; i++ ) { dp[i] = i + 1; for( int j = 0; j < i; j++ ) { if( isPalind( j, i ) ) { dp[i] = min( dp[i], dp[j-1] + 1 ); } } } for( int i = 0; i < len; i++ ) { cout << dp[i] << " "; } cout << endl; }
最近狂整DP啊,因为我发现有的时候最重要的并不是代码能力, 而是思维, 做算法的脑子一定要活, 所以我以后要狂整动态规划, 然后多学习数学, 先把思维练上来的再提高代码能力, 毕竟一道题你代码能力再强, 想不出来也是白搭。
UVA 11584 DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。