【51nod 1092】 回文字符串（区间DP）
2024-09-30 03:44:58
回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。每个字符串都可以通过向中间添加一些字符，使之变为回文字符串。
例如：abbc 添加2个字符可以变为 acbbca，也可以添加3个变为 abbcbba。方案1只需要添加2个字符，是所有方案中添加字符数量最少的。
Input
输入一个字符串Str，Str的长度 <= 1000。
Output
输出最少添加多少个字符可以使之变为回文字串。
Input示例
abbc
Output示例
2
题解
很明显的区间dp
\(dp[l][r]=min(dp[l+1][r],dp[l][r-1])+1\)
\(dp[l][r]=dp[l+1][r-1]\;if(a[l]==a[r])\)
练习了下区间dp的两种写法
记忆化搜索
import java.io.*;
import java.util.*;
public class Main {
static final int N=(int)1005;
static int dp[][]=new int[N][N];
static char a[]=new char[N];
static int solve(int l,int r) {
if(l>=r) return 0;
if(dp[l][r]!=-1) return dp[l][r];
int ans=0;
if(a[l]==a[r]) ans=solve(l+1,r-1);
else ans=Math.min(solve(l+1,r),solve(l,r-1))+1;
return dp[l][r]=ans;
}
public static void main(String[] args) {
InputStream sys=System.in;
InputReader in=new InputReader(sys);
PrintWriter out=new PrintWriter(System.out);
a=in.next().toCharArray();
for(int i=0;i<a.length;i++) Arrays.fill(dp[i], -1);
out.println(solve(0,a.length-1));
out.flush();
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
二维循环
import java.io.*;
import java.util.*;
public class Main {
static final int N=(int)1005;
static int dp[][]=new int[N][N];
static char a[]=new char[N];
public static void main(String[] args) {
InputStream sys=System.in;
InputReader in=new InputReader(sys);
PrintWriter out=new PrintWriter(System.out);
a=in.next().toCharArray();
for(int i=a.length-2;i>=0;i--) {
dp[i][i]=0;
dp[i][i+1]=(a[i]==a[i+1]?0:1);
for(int j=i+2;j<=a.length-1;j++) {
if(a[i]!=a[j])
dp[i][j]=Math.min(dp[i+1][j], dp[i][j-1])+1;
else
dp[i][j]=dp[i+1][j-1];
}
}
out.println(dp[0][a.length-1]);
out.flush();
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
最新文章
- Kafka：主要参数详解（转）
- 查看数据库表的数据量和SIZE大小的脚本修正
- Rails学习笔记一
- Android之Viewpager+Fragment实现懒加载
- 使用Spring+Junit4.4进行测试(使用注解)
- lnmp
- PHP的学习--Traits新特性
- poj 3517 约瑟夫环
- 如何找出component的注册路径
- Security:蠕虫的行为特征描述和工作原理分析
- Java EE (5) -- Java EE 6 JavaServer Faces Developer Certified Expert(1z0-896)
- HDU 3853 LOOPS 可能性dp（水
- CIC and Fir 滤波器的级联
- [UWP小白日记-15]在UWP手机端实时限制Textbox的输入
- php一些函数及方法...
- java集合系列——java集合概述（一）
- MongoDB系列四（索引）.
- 使用Docker安装Oracle数据库
- Kubernetes — 控制器
- UE4 C++ Tips