动态规划+滚动数组 -- POJ 1159 Palindrome
2023-09-27 14:27:00 时间
给一字符串,问最少加几个字符能够让它成为回文串。
比方 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]; else DP[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; }
相关文章
- 智能制造工厂三年规划
- 【LeetCode】乘积最大子数组 [M](动态规划)
- Dofbot机械臂从零部署笔记(4)——ROS之Moveit下实现实机逆向运动学规划
- 【全局规划】快速搜索随机数(RRT)
- LeetCode_动态规划_中等_152.乘积最大子数组
- LeetCode_动态规划_困难_887.鸡蛋掉落
- 《图解算法》第九章之动态规划
- LeetCode·每日一题·907.子数组的最小值之和·动态规划
- LeetCode·1143.最长公共子序列·动态规划
- LeetCode·377.组合总和 IV ·动态规划
- 动态规划0—1背包问题
- 阿里云分享日:抖6年家底儿 看未来规划
- elasticsearch系列八:ES 集群管理(集群规划、集群搭建、集群管理)
- 动态规划之滚动数组