C++ 记忆化存储

解题思路:利用一个数组记录最长的接龙数组的长度 详细在注释

注意事项:

参考代码:

#include<bits/stdc++.h>

#define int long long

using namespace std;

//找出最长接龙数组的长度 n-l就是答案

int dp[100];//以i结尾的接龙数组的长度

signed main()

{   

    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n; cin>>n;

    string tmp;

    for(int i=1;i<=n;i++){

        cin>>tmp;

        int a=tmp[0]-'0';

        int b=tmp[tmp.size()-1]-'0';

        dp[b]=max(dp[b],dp[a]+1);

    }

    int ans=0;

    for(int i=0;i<=9;i++){

        ans=max(ans,dp[i]);

    }

    ans=n-ans;

    cout<<ans;

    return 0;

}