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，找到其中最小值，即为所求的答案。
int minDeletions = Integer.MAX_VALUE; for (int i = 0; i < 10; i++) { minDeletions = Math.min(minDeletions, dp[n - 1][i]); }
代码：
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; } }
动态规划是一种常用的算法设计方法，用于解决一些特定类型的问题。它的核心思想是将问题分解为一系列子问题，并使用记忆化的方法来存储和更新状态信息，从而避免重复计算和时间复杂度的扩张。
我把动态规划的规律总结一下：
- 定义状态：首先，我们需要定义问题的状态。状态是描述问题某个特定状态的信息。状态可以是一个数字、一个数组、一个矩阵等，具体取决于问题的性质。状态的选择应该能够包含问题的所有可能情况。
- 构建状态转移方程：接下来，我们需要构建状态转移方程，描述如何从一个状态转移到另一个状态。状态转移方程是动态规划问题的核心。它是基于已知的子问题解来计算当前问题解的方法。
- 定义初始条件：在应用动态规划时，我们通常需要定义初始条件。初始条件是问题中最简单的情况，它们是解决问题的起点。初始条件的定义应该能够让状态转移方程正确运行。
- 计算最终结果：通过迭代计算状态转移方程，我们可以得到问题的最终结果。最终结果是根据问题的定义和要求得出的答案。
那么下一篇我们来看看 另一道蓝桥的真题 蜗牛
题目： 
我的代码加理解：
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轴上爬行到达该竹竿，那么时间为上一根竹竿的最短时间加上两根竹竿之间的距离。取两种情况中的最小值。
最后，输出结果，保留两位小数。
