本文主要是介绍动态规划+滚动数组 -- POJ 1159 Palindrome，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给一字符串，问最少加几个字符可以让它成为回文串，
比如 Ab3bd 最少需要两个字符可以成为回文串 dAb3bAd
思路：
动态规划 DP[i][j] 意味着从 i 到 j 这段字符变为回文串最少要几个字符，枚举子串长。
if str[i] == str[j]:
DP[i][j] = DP[i + 1][j - 1]
else:
DP[i][j] = min( DP[i + 1][j], DP[i][j - 1] ) + 1
注意：
长度较大为 5000，二维数组 5000 * 5000 需要将类型改为 short，
不需考虑 j - i < 2 的特殊情况，
因为矩阵的左下三角形会将DP[i + 1][j - 1]自动填零，
但是用滚动数组的时候需要考虑 j - i < 2，用滚动数组的时候，空间会变为 3 * 5000,
可这时候 DP 的含义稍微变下，
DP[i][j] 意味着从第 j 个字符右移 i 个长度的字符串变为回文串所需要的最少字符数目。
3.也可以用 LCS 的方法，字符串长 - LCS( 串，逆串 )
#include <iostream>
#include <cstring>
using namespace std;int nLen;
char str[5005];
short DP[5005][5005];int main(){memset( DP, 0, sizeof( DP ) );cin >> nLen;cin >> str;for( int len = 1; len < nLen; ++len ){for( int start = 0; start + len < nLen; ++start ){int end = start + len;if( str[start] == str[end] )DP[start][end] = DP[start + 1][end - 1];elseDP[start][end] = min( DP[start + 1][end], DP[start][end - 1] ) + 1;}}cout << DP[0][nLen - 1];return 0;
}滚动数组 715K：
#include <iostream>
#include <cstring>
using namespace std;int nLen;
char str[5005];
short DP[3][5005];int main(){memset( DP, 0, sizeof( DP ) );cin >> nLen;cin >> str;for( int len = 1; len < nLen; ++len ){for( int start = 0; start + len < nLen; ++start ){int end = start + len;if( str[start] == str[end] && ( end - start >= 2 ) )DP[len % 3][start] = DP[( len - 2 ) % 3][start + 1];else if( str[start] != str[end] )DP[len % 3][start] = min( DP[( len - 1 ) % 3][start + 1],DP[( len - 1 ) % 3][start] ) + 1;}}cout << DP[(nLen - 1) % 3][0];return 0;
}
这篇关于动态规划+滚动数组 -- POJ 1159 Palindrome的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
