首页 > 代码库 > 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;
}
View Code

  最近狂整DP啊,因为我发现有的时候最重要的并不是代码能力, 而是思维, 做算法的脑子一定要活, 所以我以后要狂整动态规划, 然后多学习数学, 先把思维练上来的再提高代码能力, 毕竟一道题你代码能力再强, 想不出来也是白搭。 

 

UVA 11584 DP