动态规划 接龙数列
我打眼一看感觉得用栈stack，取出首位和末位全都入栈，每次弹出栈顶，获取此时的栈顶并弹出和下一个栈顶比较。整了老半天发现不行，原来是我脑子瓦特了。虽然没有用栈解决这道问题，但是，栈和队列都是非常重要的只是，不了解的同学们可以去学习一下，下面有传送门。栈与队列知识点（我看着学的栈和队列，很不错）。
相反，它是一道动态规划类的问题。题目要求的是最少的删除个数，那咱们就可以使用动态规划求出最长的接龙数字长度，最后在用数组长度减去最长的接龙数字长度。因此，动态规划就是这道题的重点。然而状态转移方程又是动态规划的重点，因此只要我们写出状态转移方程，这道题就迎刃而解了。
让我们用原题的举例来看一下，
11 121 22 12 2023（数列）
1 1 1 1 2 2 1 2 2 3 （首位 末位）
我们首先建立一个存放数字末位的数组 dp[10] (十进制数字结尾只可能是0到9，所以我们开的数组长度为10)。每次比较以末尾为dp数组下标的值与以首位为dp数组下标的值+1，并将更大的值赋给以末尾为dp数组下标的元素。
用a来表示首位，用b来表示末位，既动态转移方程就是： dp[b]=std::max(dp[b],dp[a]+1);
由此，我们再写代码：
#include<iostream>
#include<cstring>
#include<cmath>
#define int long long
#define endl "\n"
#define ios std::ios::sync_with_stdio(0),std::cin.tie(0),std::cout.tie(0)
int n,dp[10];
void solve()
{
std::cin>>n;
int ans=0;
for(int i=0;i<n;i++)
{
std::string s;std::cin>>s;
int a=s[0],b=s[s.size()-1];
dp[b]=std::max(dp[b],dp[a]+1);
ans=std::max(dp[b],ans);
}
std::cout<<n-ans<<endl;
}
signed main()
{
ios;
solve();
return 0;
}动态规划就是这样，想的多，但是写的话只有很少一部分。同时，动态规划类问题没有啥捷径，唯一的捷径就是做题做题再做题。
最后，希望可以帮到大家。
标签：std,int,c++,蓝桥,接龙,数组,动态,dp From： https://blog.csdn.net/2401_83357065/article/details/137292635