POJ 1159题意:
回文词是一种对称的字符串。任意给定一个字符串,通过插入若干字符,都可以变成回文词。现在的任务是,求出将给定字符串变成回文词所需要插入的最少字符数。比如:“Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”,但是插入少于2个的字符无法变成回文词。
[输入]:
第一行:字符串的长度N(3 <= N <= 5000)
第二行:需变成回文词的字符串
[输出]:
将给定字符串变成回文词所需要插入的最少字符数
[样例]:
Sample Input
5
Ab3bd
Sample Output
2
分析:
S和S' (注:S'是S的反串)的最长公共子串其实一定是回文的。这样我们就可以借助lcs来解决该题,即用s的长度减去lcs的值即可。
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader in = new BufferedReader(new InputStreamReader (System.in));
int total = Integer.parseInt(in.readLine());
String string = in.readLine();
System.out.println(total-LCS(string,new StringBuffer(string).reverse().toString()));
}
//返回两个string的lcs的长度
public static int LCS(String str1,String str2){
short length1 = (short)str1.length();
short length2 = (short)str2.length();
short[][]result = new short [2][length2+1]; //滚动数组,节省空间
for(int i=1;i<=length1;i++){
for(int j=1;j<=length2;j++){
if(str1.charAt(i-1)==str2.charAt(j-1))
result[i%2][j] = (short)(result[(i-1)%2][j-1]+1);
else
result[i%2][j] = result[(i-1)%2][j]>result[i%2][j-1]?result[(i-1)%2][j]:result[i%2][j-1];
}
}
return result[length1%2][length2];
}
}
源码:
分享到:
相关推荐
6. **动态规划优化**:记忆化搜索、状态压缩、滚动数组等。 7. **贪心算法**:如何在每一步选择最优解,解决背包问题、约瑟夫环等。 8. **模拟**:根据题目描述,编写程序模拟过程。 9. **编码技巧**:输入输出的...
在动态规划的问题上,有的解法可能会使用记忆化搜索来优化递归过程,而有的则可能利用滚动数组来减少空间复杂度。通过对比这些代码的异同,我们可以从中汲取更多的编程灵感和策略,进一步丰富自己的解题宝库。 除此...
对于特定情况,如POJ 2823 Sliding Window问题,可以通过滚动数组来减少内存需求,当区间长度固定时,仅保留一个dp[i][k]即可。 LCA问题则涉及树的数据结构,寻找两个节点的最近公共祖先。例如,树中的节点A、B、C....
此外,还可以通过滚动数组(Sliding Window)优化特定情况下的空间占用,如POJ 2823问题。 **LCA(Least Common Ancestors)** LCA,最近公共祖先,是图论中的一个重要概念,通常应用于树状结构。给定树中的两个...