題目

解析

這題沒思路，壓根沒想到DP 😦

看了大神的題解，利用dp記錄每一個數結尾的長度，最后再用N-dp中的最大值，得到最少刪除數

動態規劃（DP）是一種解決復雜問題的算法思想，它的核心是 將大問題拆解為小問題，并記錄中間結果避免重復計算。

什么時候該用 DP？

1.求最值問題
最長遞增子序列、最短路徑、最大利潤、最少操作次數等。
例如本題的「最長接龍序列」，最終答案需要求最值。

2.問題可以被分解為重疊子問題
子問題之間有重復計算的部分。
例如斐波那契數列：fib(n) = fib(n-1) + fib(n-2)，計算 fib(5) 需要重復計算 fib(3)。

3.子問題的最優解能推導出全局最優解（最優子結構）
當前狀態的值只依賴于前面已計算的狀態。
例如本題中，以數字 y 結尾的最長接龍序列長度，只依賴于前面以 x 結尾的序列長度。

動態規劃 vs 其他方法

貪心算法
貪心每一步選擇當前最優，但不能保證全局最優（例如部分背包問題可用貪心，但 0-1背包不行）。
DP 能保證全局最優，但可能需要更高時間復雜度。

回溯/DFS
回溯會遍歷所有可能路徑，時間復雜度高；DP 通過記錄中間結果避免重復計算。

代碼

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
#include <map>
using namespace std;
int n, dp[10];int main() {cin >> n;for (int i = 0; i < n; i++) {string s;//便于找到首尾數cin >> s;//如果當前字符串 s 的首位是 x，那么它只能接在某個以 x 結尾的序列后面，形成新的以 y 結尾的序列。//以數字 y 結尾的最長接龍序列長度，只依賴于前面以 x 結尾的序列長度。(x：S的首位，y:為S的末位)//之前以x結尾的長度     =max(之前以x結尾的長度    ,之前以y結尾的長度+1)dp[s.back() - '0'] = max(dp[s.back() - '0'], dp[s.front() - '0']  + 1);}int maxx = INT_MIN;for (int i = 0; i < 10; i++)maxx = max(maxx, dp[i]);cout << n - maxx;return 0;
}