字符串删除回文串面试题
题目大意：给定一个字符串，每次可以删除一个连续回文，最少几次将删完字符串。
思路
区间DP，$dp[l][r]$ 表示删除字符串 $l\cdots r$ 需要的最小代价。
我们可以将删除回文串的过程看作不断剥离回文串两段的相同字母，因为每一次删除回文串的代价均为 1，我们可以将删除回文串的代价记在删除回文串中心上，剥离非中心的两个相同字母不需要代价。
状态转移方程在普通区间DP合并的基础上，增加了 0 代价剥离区间边缘两个相同字母的情况。
初始化为长度为 1 与长度为 0 的区间代价为 1。
详细思路可以见代码
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <stdio.h> #include <algorithm> using namespace std; // 给你一个字符串，每次可以删除连续的回文串，问你最少多少次可以将这个字符串删除完 const int MAXN = 1050; int dp[MAXN][MAXN]; int dfs(int l, int r, int s[]){ if (r - l + 1 <= 1) return 1; if (dp[l][r] != -1) return dp[l][r]; dp[l][r] = r - l + 1; for (int i = l; i < r; i++) dp[l][r] = min(dfs(l, i, s) + dfs(i + 1, r, s), dp[l][r]); if (s[l] == s[r]) dp[l][r] = min(dp[l][r], dfs(l + 1, r - 1, s)); return dp[l][r]; } int points(int input1, int input2[]) { int n = input1; for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) dp[i][j] = -1; return dfs(0, n - 1, input2); } int main(){ int arr[] = {1, 4, 3, 1, 5}; printf("%d\n", points(5, arr)); return 0; } |
原文链接：字符串删除回文串面试题
WNJXYKの博客 版权所有，转载请注明出处。
坑神，我思路是预处理出某个点开始最长回文串。然后再进行区间dp.考虑最后一步。要么是将区间划成两部分。要么是挖去中间一个回文串去转移。你觉得正确么哈哈你的方法还是简洁一些
好吧，意识到我错了