P9242-蓝桥杯-2023-省-B-接龙数列-DP巧妙解决接龙问题
目录
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;
}