目录
题目
思路
代码
题目
思路
这个题求最少删除多个个数，其实是求最长的接龙数列，用总个数-接龙数列的个数就是最少删除的个数。
那么如何求解最长的接龙数列的问题。
思考，每个数都有选或不选的两种选项（选：可以接龙前面；不选：自己本身作为一个接龙数列）。可以想到是 动态规划问题。
然后我就写代码了，时间复杂度是O(n^2)，只能过一半的数据。（ps：我以为是01背包问题，但是状态表示出来又不是，没想到是最长上升子序列问题）
后面发现是最长上升子序列的问题，因为后面的数都受前面的数的影响，因此DP分析与最长上升子序列相同，就如上图所示。
2024/3/5打卡最长上升子序列**----线性DP，贪心，单调栈-CSDN博客
// 只能过一半的版本，超时
import java.io.*;
import java.util.*;
class Main{
static int N = 100010;
static int n;
static String[] a = new String[N];
static int[] f = new int[N];
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(in.readLine());
String[] s = in.readLine().split(" ");
f[0] = 1; // 自己本身也可以作为接龙数列
for(int i=1;i<n;i++){
f[i] = 1;
for(int j=0;j<i;j++){ // 从 0~i-1，看前面的是否能接龙当前数字
if (s[j].charAt(s[j].length() - 1) == s[i].charAt(0)) { // 即前面的数的最右边的数字是否跟当前这个数最左边的数相同
f[i] = Math.max(f[i], f[j] + 1); // 相同的话就取最大值
}
}
}
int res = 0;
for(int i=0;i<n;i++) res = Math.max(res,f[i]);
System.out.println(n-res);
}
}因为 N 的范围是100000，因此要保证在O(nlogn)范围内 。
只能优化第二重循环。可以发现的是第二重循环我们没有必要每一个都遍历一遍，
- 1.有些根本不能接龙上，
- 2.接上也有可能被后面的更长的数列更新掉。
因此如果到第 i 个数，我们只需要找 以 i 的左边第一个数结尾的接龙数列的最大长度以及数的位置。
用position[ ] 记录以 [0~9] 结尾的接龙数列的最远位置
用p_max[ ] 记录以 [0~9] 结尾的接龙数列的最大长度（最大长度对应的位置就是相应的最远位置）
代码
有些乱 ，看注释就懂了
import java.io.*;
import java.util.*;
class Main{
static int N = 100010;
static int n;
static int[] position = new int[10]; // 存储以 [0~9] 结尾的接龙长度最大的位置
static int[] p_max = new int[10]; // 存储以 [0~9] 结尾的接龙长度最大的长度
static int[] f = new int[N]; // dp
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(in.readLine());
String[] s = in.readLine().split(" ");
Arrays.fill(position,-1); // 因为数组从0 来说，所以我需要初始化position，
f[0] = 1; // 单独一个也算一个长度接龙
position[Integer.parseInt(String.valueOf(s[0].charAt(s[0].length()-1)))] = 0; // 第一个数的个位数位置
p_max[Integer.parseInt(String.valueOf(s[0].charAt(s[0].length()-1)))] = 1; // 以第一个数的个位数结尾的最大长度的个数
for(int i=1;i<n;i++){
f[i] = 1;
int tail = Integer.parseInt(String.valueOf(s[i].charAt(s[i].length()-1))); // 取出最右边的数
int front = Integer.parseInt(String.valueOf(s[i].charAt(0))); // 最左边的数
int mx = position[front]; // 以左边的数字结尾的最远位置
if(mx!=-1) // 如果有接龙数列的话
f[i] = f[mx]+1;
if(f[i]>=p_max[tail]){ // 如果以i最右边的数结尾的接龙数列长度大于当前的长度，更新以tail结尾的结论数列
position[tail] = i;
p_max[tail] = f[i];
}
}
int res = 0;
for(int i=0;i<n;i++) res = Math.max(res,f[i]);
System.out.println(n-res);
}
}
