题解 | 相助(easy)

#include<bits/stdc++.h>
#define INF 0x3fffffff
#define endl '\n'
using namespace std;

void solve() {
    int n;cin >> n;
    vector<int> dp(n+1);
    vector<int> nums(2,INF);
    int x;
    for(int i = 1;i<=n;i++) {
        cin >> x;
        dp[i] = nums[x]+1;
        nums[x] = min(nums[x],dp[i-1]);
    }
    if(dp[n] > n) cout << -1 << endl;
    else cout << dp[n] << endl;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int t = 1;
    while(t--) {
        solve();
    }
    return 0;
}

看了一下别人的解析，还有比较思维的做法？

动态规划还是很好看出来的，每次往队尾添加新元素时，必须保证新元素可以旧元素匹配，否则就是-1，同时贪心选择最小的旧元素就好了