接龙数列
原题链接
解题思路
- 状态表示为 f[i, j]
- 前 i 个数里(选择第 i 个数)
- 接龙数列末尾数的末尾数字为 j
- 存储满足 i j 状态最长接龙数列的长度
- 状态转移方程
- f[i] 对比 f[i - 1] 唯一不同的可能就是 f[i, b]
- 方程:f[i, b] = max(f[i, b], f[i - 1, a] + 1]
优化
由于该状态转移方程计算 i 只涉及到了 i - 1,因此我们可以将状态表示数组优化成一维
时间复杂度 $ O(n) $
C ++ 代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int f[10];
string s;
int main()
{
ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
cin >> n;
int maxe = 0;
for (int i = 1; i <= n; i ++ )
{
cin >> s;
int a = s[0] - '0', b = s.back() - '0';
f[b] = max(f[b], f[a] + 1), maxe = max(maxe, f[b]);
}
cout << n - maxe << endl;
return 0;
}