dp + 滚动数组思想

解题思路:dp[i][j]代表选到第i个时，要使此时结尾位为j，需要删除的个数。如果j≠num[i]的末尾，那么只能删除第i个数，此时dp[i][j] = dp[i - 1][j] + 1；否则，就有两种选择，删除或者加上这个数。因此就有状态转移方程dp[i][j] = min(dp[i - 1][j],dp[i - 1][h[i]])，其中，h[i]代表第i个数的首位。

我们可以发现每一位的dp都只和前一项有关，因此我们可以减少使用的空间，使用两个数组就能完成dp。

话不多说，上代码

注意事项:

参考代码:

#include <bits/stdc++.h>
#define endl "\n"
#define min(a,b) a < b ? a : b
using namespace std;
const int N = 1e5 + 5;
int n,dp[10],h[N],t[N],res = N;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(dp,0,sizeof(dp));
    cin>>n;
    for(int i = 1;i <= n;i++)
    {
        string s;cin>>s;
        h[i] = s[0] ^ 48;//获取首位
        t[i] = s[s.size() - 1]  ^ 48;//获取末位
    }
    for(int i = 1;i <= n;i++)
    {
        int dp_copy[10];
        for(int j = 0;j < 10;j++)
            dp_copy[j] = dp[j] + 1; //先删除该数字
        dp_copy[t[i]] = min(dp_copy[t[i]],dp[h[i]]);//每一个的数字的头等于前一个龙的尾时可以选择加上这一个数
        for(int j =0;j < 10;j++)
            dp[j] = dp_copy[j];//迭代
    }
    for(int i = 0;i < 10;i++)
        res = min(res,dp[i]);//最小的删除的数就是答案
    cout<<res;
    return 0;
}