本文讲解动态规划！ 蓝桥真题实战：数组接龙＋蜗牛
2023年蓝桥杯Java组b组I：
题目一：接龙数组
题目描述： 对于一个长度为K的整数数列：A1, A2, ..., AK，我们称之为接龙数列当且仅当Ai的首位数字恰好等于Ai−1的末位数字（2 ≤ i ≤ K）。例如12, 23, 35, 56, 61, 11是接龙数列；12, 23, 34, 56不是接龙数列，因为56的首位数字不等于34的末位数字。所有长度为1的整数数列都是接龙数列。现在给定一个长度为N的数列A1, A2, ..., AN，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？ 输入格式： 第一行包含一个整数N。 第二行包含N个整数A1, A2, ..., AN。 输出格式： 一个整数代表答案。 样例输入： 5 11 121 22 12 2023 样例输出： 1 提示： 删除22，剩余11, 121, 12, 2023是接龙数列。
最道题咋一看是贪心 实则却是动态规划
正常情况下 两遍遍历这道题的时间复杂度应该是n方的 但是这样显然无法通过所有测试点 于是 我们使用动态规划的思想 来进行优化这道题
首先，我们定义一个二维数组 dp，其中 dp[i][j] 表示前 i 个接龙数组以数字 j 结尾的最少删除个数。
接下来，我们考虑状态转移方程。对于 dp[i][j]，有两种情况：
- 如果前
i个数的末尾数字是left，末尾数字是right，那么dp[i][j]可以通过删除第i个数字或者保留第i个数字得到。因此，我们可以得到状态转移方程：dp[i][j] = min(dp[i - 1][left], dp[i][j])。 - 要么把前
i个数都删了，要么就是它本身，所以有dp[i][j] = min(dp[i][j], i)。
最后，我们对于最后一位 dp[n-1][i]，遍历 i 从 0 到 9，找到其中最小值，即为所求的答案。
代码语言：javascript复制int minDeletions = Integer.MAX_VALUE;
for (int i = 0; i < 10; i ) {
minDeletions = Math.min(minDeletions, dp[n - 1][i]);
}代码：
代码语言：javascript复制import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i ) {
arr[i] = scanner.nextInt();
}
int result = minDelete(n, arr);
System.out.println(result);
}
public static int minDelete(int n, int[] arr) {
// 定义dp数组
int[][] dp = new int[n][10];
for (int i = 0; i < n; i ) {
dp[i][0] = i;
}
for (int j = 1; j <= 9; j ) {
for (int i = 0; i < n; i ) {
int left = arr[i] % 10; // 当前数的末尾数字
int right = arr[i-1] / 10; // 上一个数的首位数字
if (left == right) {
dp[i][j] = Math.min(dp[i-1][left], dp[i][j]);
}
dp[i][j] = Math.min(dp[i][j], i);
}
}
// 计算最少删除的个数
int ans = Integer.MAX_VALUE;
for (int i = 0; i < n - 1; i ) {
ans = Math.min(ans, dp[i][0]);
}
return ans;
}
}动态规划是一种常用的算法设计方法，用于解决一些特定类型的问题。它的核心思想是将问题分解为一系列子问题，并使用记忆化的方法来存储和更新状态信息，从而避免重复计算和时间复杂度的扩张。
我把动态规划的规律总结一下：
- 定义状态：首先，我们需要定义问题的状态。状态是描述问题某个特定状态的信息。状态可以是一个数字、一个数组、一个矩阵等，具体取决于问题的性质。状态的选择应该能够包含问题的所有可能情况。
- 构建状态转移方程：接下来，我们需要构建状态转移方程，描述如何从一个状态转移到另一个状态。状态转移方程是动态规划问题的核心。它是基于已知的子问题解来计算当前问题解的方法。
- 定义初始条件：在应用动态规划时，我们通常需要定义初始条件。初始条件是问题中最简单的情况，它们是解决问题的起点。初始条件的定义应该能够让状态转移方程正确运行。
- 计算最终结果：通过迭代计算状态转移方程，我们可以得到问题的最终结果。最终结果是根据问题的定义和要求得出的答案。
那么下一篇我们来看看 另一道蓝桥的真题 蜗牛
题目：
我的代码加理解：
代码语言：javascript复制public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] x = new int[n 1]; // 每根杆的横坐标
int[] origin = new int[n 1]; // 传送出发点的高度
int[] dest = new int[n 1]; // 传送到达点的高度
// 读入每根杆的横坐标
for (int i = 1; i <= n; i ) {
x[i] = scan.nextInt();
}
// 读入传送出发点和到达点的高度
for (int i = 1; i < n; i ) {
origin[i] = scan.nextInt();
dest[i 1] = scan.nextInt();
}
// 动态规划dp数组
double[][] dp = new double[n 1][2];
dp[1][0] = dp[1][1] = x[1]; // 第一根杆只能爬过去
for (int i = 2; i <= n; i ) {
// 计算去传送出发点的时间，可以从传送到达点出发，也可以从x轴出发
//这里计算的是 如果选择了传送 上一个的到达点 到 本杆的传送点的时间 有两种情况
// ①到达点高需要往下走到传送点
//②传送点高需要往上走到传送点
double transferTime = origin[i - 1] > dest[i - 1] ? (origin[i - 1] - dest[i - 1]) / 0.7
: (dest[i - 1] - origin[i - 1]) / 1.3;
// 这里假设上一杆到当前杆选择了传送的情况 就是两种情况 上上杆要么到达上一杆使用传送要么就走路
//①到达上一杆使用的是传送，他并不是从底部往上爬 而是在上上杆传送过来的，那么就要加上 上一到达点到本次传送点的距离（上一步计算的）
//②到达上一杆使用的是走路 所以要加上从上一杆的底部爬到传送点的时间 也就是到达上一杆的最短时间加上向上爬的时间
//取最小值
transferTime = Math.min(dp[i - 1][1] transferTime, dp[i - 1][0] origin[i - 1] / 0.7);
// 到达(X_i,0)所花时间
//0意味着他要选择走路 所以在这一条计算中 目标是走到该轮杆子的 底部
//所以 有两种情况：
//①要么是 上一轮杆子选择传送到这个杆子的目标点（这里的时间就是transferTime） 加上从这个传送点上面下来的时间
//②要么是 上一轮杆子选择走路到这个杆子，所以就是到达上一轮杆子的最短时间加上两杆之间的距离
dp[i][0] = Math.min(transferTime dest[i] / 1.3, dp[i - 1][0] x[i] - x[i - 1]);
// 到达第i根竹竿上的传送到达点所花时间
//1意味着在这根杆子上他要选择传送 所以这一条计算的目标是他要走到本杆的传送点
//那么就有两种情况：
//①要么上一轮杆子选择了传送，所以就是刚才计算的到达下一杆的传送点的时间
//②要么上一轮杆子选择了走路，所以就是到达上一轮杆子的最短时间加上上爬到传送点的时间
dp[i][1] = Math.min(transferTime, dp[i][0] dest[i] / 0.7);
}
// 保留两位小数输出结果，即dp[n][0]
System.out.println(String.format("%.2f", dp[n][0]));
}
}思路解析
首先，读入输入数据，包括竹竿的数量n，每根竹竿的横坐标x，以及传送出发点和到达点的高度origin和dest。 接下来，定义一个二维数组dp，用于存储状态转移的结果。dp[i][j]表示蜗牛到达第i根竹竿的状态，其中j=0表示蜗牛在竹竿上爬行，j=1表示蜗牛选择传送到达。 然后，对于第一根竹竿，蜗牛只能选择在x轴上爬行，所以dp[1][0]和dp[1][1]都等于x[1]，即第一根竹竿的横坐标。 接下来，从第2根竹竿开始进行动态规划。对于每根竹竿，计算到达该竹竿的最短时间。 首先，计算蜗牛从上一根竹竿传送到达该竹竿的时间。这里有两种情况：如果传送点高度高于上一根竹竿的到达点高度，蜗牛需要爬下来，所以时间为(传送点高度-到达点高度)/0.7；如果传送点高度低于上一根竹竿的到达点高度，蜗牛需要爬上去，所以时间为(到达点高度-传送点高度)/1.3。取两种情况中的最小值。 然后，计算蜗牛到达该竹竿底部的时间。这里也有两种情况：如果上一根竹竿选择传送到达该竹竿的目标点，那么时间为传送时间加上从传送点爬下来的时间；如果上一根竹竿选择在x轴上爬行到达该竹竿，那么时间为上一根竹竿的最短时间加上两根竹竿之间的距离。取两种情况中的最小值。 最后，输出结果，保留两位小数。
