要求:前一个数结尾字母和下一个数第一个字母一样
类似最长子序列
闫氏dp:1,状态记录以i结尾的子序列长度 2,属性:求最长子序列
结尾输出总数减去最长子序列长度
1 #include<bits/stdc++.h> 2 using namespace std; 3 int dp[10];//dp[i]储存以i为结尾的最长子序列 4 int main() 5 { 6 int n;cin>>n; 7 int maxn=0; 8 for(int i=0;i<n;i++) 9 { 10 string s;cin>>s; 11 int a=s[0]-'0',b=s.back()-'0';a为字符串第一个数,b为最后一个数 12 dp[b]=max(dp[b],dp[a]+1);状态更新 13 maxn=max(maxn,dp[b]); 14 } 15 cout<<n-maxn<<endl; 16 }