P9242 [蓝桥杯 2023 省 B] 接龙数列--DP【巧妙解决接龙问题】

题目

解析

这题没思路，压根没想到DP 😦

看了大神的题解，利用dp记录每一个数结尾的长度，最后再用N-dp中的最大值，得到最少删除数

动态规划（DP）是一种解决复杂问题的算法思想，它的核心是 将大问题拆解为小问题，并记录中间结果避免重复计算。

什么时候该用 DP？

1.求最值问题
最长递增子序列、最短路径、最大利润、最少操作次数等。
例如本题的「最长接龙序列」，最终答案需要求最值。

2.问题可以被分解为重叠子问题
子问题之间有重复计算的部分。
例如斐波那契数列：fib(n) = fib(n-1) + fib(n-2)，计算 fib(5) 需要重复计算 fib(3)。

3.子问题的最优解能推导出全局最优解（最优子结构）
当前状态的值只依赖于前面已计算的状态。
例如本题中，以数字 y 结尾的最长接龙序列长度，只依赖于前面以 x 结尾的序列长度。

动态规划 vs 其他方法

贪心算法
贪心每一步选择当前最优，但不能保证全局最优（例如部分背包问题可用贪心，但 0-1背包不行）。
DP 能保证全局最优，但可能需要更高时间复杂度。

回溯/DFS
回溯会遍历所有可能路径，时间复杂度高；DP 通过记录中间结果避免重复计算。

代码

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
#include <map>
using namespace std;
int n, dp[10];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;//便于找到首尾数
		cin >> s;

	//如果当前字符串 s 的首位是 x，那么它只能接在某个以 x 结尾的序列后面，形成新的以 y 结尾的序列。
	//以数字 y 结尾的最长接龙序列长度，只依赖于前面以 x 结尾的序列长度。(x：S的首位，y:为S的末位)

	//之前以x结尾的长度     =max(之前以x结尾的长度    ,之前以y结尾的长度+1)
		dp[s.back() - '0'] = max(dp[s.back() - '0'], dp[s.front() - '0']  + 1);
	}
	
	int maxx = INT_MIN;
	for (int i = 0; i < 10; i++)
		maxx = max(maxx, dp[i]);
	cout << n - maxx;
	return 0;
}