【冲击蓝桥篇】动态规划（上）：真题实战＋思路解析

 🎉🎉欢迎光临🎉🎉

🏅我是苏泽，一位对技术充满热情的探索者和分享者。🚀🚀

🌟特别推荐给大家我的最新专栏《数据结构与算法：初学者入门指南》📘📘

希望能和大家一起学习！共同进步！

这是苏泽的个人主页可以看到我其他的内容哦👇👇

努力的苏泽http://suzee.blog.csdn.net

 本文讲解动态规划！ 蓝桥真题实战：数组接龙＋蜗牛  

正片

目录

 本文讲解动态规划！ 蓝桥真题实战：数组接龙＋蜗牛  

2023年蓝桥杯Java组b组I：

题目一：接龙数组

首先，我们定义一个二维数组 dp，其中 dp[i][j] 表示前 i 个接龙数组以数字 j 结尾的最少删除个数。

接下来，我们考虑状态转移方程。对于 dp[i][j]，有两种情况：

最后，我们对于最后一位 dp[n-1][i]，遍历 i 从 0 到 9，找到其中最小值，即为所求的答案。

我把动态规划的规律总结一下：

那么下一篇我们来看看 另一道蓝桥的真题 蜗牛

我的代码加理解：

思路解析 

---

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]，有两种情况：

1. 如果前 i 个数的末尾数字是 left，末尾数字是 right，那么 dp[i][j] 可以通过删除第 i 个数字或者保留第 i 个数字得到。因此，我们可以得到状态转移方程：dp[i][j] = min(dp[i - 1][left], dp[i][j])。
2. 要么把前 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  
 
代码：
 
 
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