本文讲解动态规划！ 蓝桥真题实战：数组接龙＋蜗牛
正片
目录
首先，我们定义一个二维数组 dp，其中 dp[i][j] 表示前 i 个接龙数组以数字 j 结尾的最少删除个数。
接下来，我们考虑状态转移方程。对于 dp[i][j]，有两种情况：
最后，我们对于最后一位 dp[n-1][i]，遍历 i 从 0 到 9，找到其中最小值，即为所求的答案。
2023年蓝桥杯Java组b组I：
题目一：接龙数组
最道题咋一看是贪心 实则却是动态规划
正常情况下 两遍遍历这道题的时间复杂度应该是n方的 但是这样显然无法通过所有测试点 于是 我们使用动态规划的思想 来进行优化这道题
首先，我们定义一个二维数组 dp，其中 dp[i][j] 表示前 i 个接龙数组以数字 j 结尾的最少删除个数。
接下来，我们考虑状态转移方程。对于 dp[i][j]，有两种情况：
最后，我们对于最后一位 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]));
}
}