1、最长公共子序列
算法分析
image.png
时间复杂度)
Java 代码
import java.util.Scanner;
public class Main {
static int N = 1010;
static int n,m;
static int[][] f = new int[N][N];
static char[] a = new char[N];
static char[] b = new char[N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String s1 = scan.next();
n = s1.length();
for(int i = 1;i <= n;i ++) a[i] = s1.charAt(i - 1);
String s2 = scan.next();
m = s2.length();
for(int i = 1;i <= m;i ++) b[i] = s2.charAt(i - 1);
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
{
f[i][j] = Math.max(f[i - 1][j],f[i][j - 1]);
if(a[i] == b[j])
f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
}
System.out.println(f[n][m]);
}
}
2、回文串
算法分析
区间dp
从当前样子变成初始状态需要添加字母的数量 等价于 当前样子变成最大的回文串需要剪去的字母的数量
即至少减去多少字母 等价于 总数量 - 最大回文子序列的长度
状态计算的选择方式和最长公共子序列类似
dbeb2ca84e7ee6b21319802cbd0170d.png
时间复杂度
Java 代码
import java.util.Scanner;
public class Main {
static int N = 1010;
static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String s = scan.next();
int n = s.length();
for(int len = 1;len <= n;len ++)
{
for(int i = 0;i + len - 1 < n;i ++)
{
int j = i + len - 1;
if(len == 1) f[i][j] = 1;
else
{
f[i][j] = Math.max(f[i][j - 1], f[i + 1][j]);
if(s.charAt(i) == s.charAt(j)) f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + 2);
}
}
}
System.out.println(n - f[0][n - 1]);
}
}
3、蒜头君的日志
算法分析
题目抽象出来是一个最长公共上升子序列问题
image.png
优化：
由于状态转移时每次需要用到前缀的信息计算出来的信息(最大值)，因此在枚举a[]数组每个元素时，用maxv记录当前a[i] > 所有b[k]时，f[k] + 1的最大值，其中k < j，可以降到二维的复杂度
时间复杂度 )
Java 代码1
import java.util.Scanner;
public class Main {
static int N = 3010;
static int[] a = new int[N];
static int[] b = new int[N];
static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 1;i <= n;i ++) a[i] = scan.nextInt();
for(int i = 1;i <= n;i ++) b[i] = scan.nextInt();
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= n;j ++)
{
f[i][j] = f[i - 1][j];
if(a[i] == b[j])
{
f[i][j] = 1;//初始为1
for(int k = 1;k < j;k ++)
{
if(b[k] < b[j]) f[i][j] = Math.max(f[i][j], f[i - 1][k] + 1);
}
}
}
}
//需要类似最长上升子序列求得最大值,也可以直接加到上面的循环中
int res = 0;
for(int i = 1;i <= n;i ++) res = Math.max(res,f[n][i]);
System.out.println(res);
}
}
时间复杂度
Java 代码2
import java.util.Scanner;
public class Main {
static int N = 3010;
static int[] a = new int[N];
static int[] b = new int[N];
static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 1;i <= n;i ++) a[i] = scan.nextInt();
for(int i = 1;i <= n;i ++) b[i] = scan.nextInt();
for(int i = 1;i <= n;i ++)
{
int maxv = 1;//记录当前a[i] > 所有b[k]时，f[k] + 1的最大值，其中k < j
for(int j = 1;j <= n;j ++)
{
f[i][j] = f[i - 1][j];
if(a[i] == b[j]) f[i][j] = maxv;
if(b[j] < a[i]) maxv = Math.max(maxv, f[i][j] + 1);
}
}
//需要类似最长上升子序列求得最大值,也可以直接加到上面的循环中
int res = 0;
for(int i = 1;i <= n;i ++) res = Math.max(res,f[n][i]);
System.out.println(res);
}
}
4、蒜头君的密码文件
算法分析
最短编辑距离
image.png
时间复杂度
Java 代码
import java.util.Scanner;
public class Main {
static int N = 1010;
static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String s1 = " " + scan.next();
String s2 = " " + scan.next();
int n = s1.length() - 1;
int m = s2.length() - 1;
for(int i = 0;i <= n;i ++) f[i][0] = i;
for(int i = 0;i <= m;i ++) f[0][i] = i;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
{
f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if(s1.charAt(i) == s2.charAt(j)) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
}
System.out.println(f[n][m]);
}
}
网友评论