E-相依

定义dp[i]为第一个数到第i个数所需要合并的最少次数，可以得到动态转移方程：

dp[i] = min{dp[j - 1] + 1} (1 <= j < i且 val[i] = val [j]且 dp[j - 1]存在)

但是这样做要枚举前i - 1个数，时间复杂度原地爆炸。观察动态转移方程，不难发现我们要找的是dp[j - 1]的最小值，即每个与i位置有相同的值的j位置前面一个位置的dp值的最小值。所以可以使用哈希表记录每个val值前面位置dp值的最小值，用m[val]代表这个值,那么dp[i]就可以这样计算:

dp[i] = m[val[i]] + 1

现在，只需要在每次计算完当前i位置的dp值后更新val值，就可以用o(n)的时间复杂度完成本题了

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define MAXN 1000000000
int arr[1000000];
int dp[1000000];
int n;
unordered_map<int, int> valm;

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
	}
	dp[0] = 0;
	for(int i = 1; i <= n; i++) {
		//计算当前dp值
		dp[i] = MAXN;
		if(valm.find(arr[i]) != valm.end()) {
			dp[i] = valm[arr[i]] + 1;
		}
		//更新最小val值
		if(dp[i - 1] == MAXN) continue;
		if(valm.find(arr[i]) == valm.end()) {
			valm[arr[i]] = dp[i - 1];
		} else {
			valm[arr[i]] = min(valm[arr[i]], dp[i - 1]);
		}
		
	}
	if(dp[n] == MAXN) {
		cout << "-1";
		return 0;
	}
	cout << dp[n];
	return 0;
}