算法1

（按最长上升子序列）会TLE

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;

int n;
int first[N],last[N];
int f[N];

int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;++i){
        string s;
        cin >> s;
        first[i] = s[0] - '0';
        last[i] = s[s.size()-1] - '0';
    }

    for(int i=1;i<=n;++i){
        f[i] = 1;
        for(int j=1;j<i;++j){
            if(first[i] == last[j]) f[i] = max(f[i],f[j] + 1);
        }
    }

    int res = 0;
    for(int i=1;i<=n;++i){
        res = max(res,f[i]);
    }
    cout << n - res;


    return 0;
}

dp分析

算法2

优化代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;

int n;
int g[10]; // 辅助数组 用于优化

int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;

    int res = 0;
    for(int i=1;i<=n;++i){
        string s;
        cin >> s;
        // first,last都只用一次，都无需存到数组中
        int first = s[0] - '0',last = s[s.size()-1] - '0';

        int f = 1;// f[i]只用一次，所以可以优化掉
        f = max(f,g[first] + 1); // 以第i个数的开头为结尾的数 其作为接龙数列最后一个数
        g[last] = max(g[last],f); // 同时以第i个数为结尾的数列最大长度也要更新
        res = max(res,f);
    }
    cout << n - res;

    return 0;
}