algo-aha

两等长序列的对应数可交换，使两序列都严格递增的最小交换数

• https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/

int minSwap(vector<int>& A, vector<int>& B) {
    // 设dp[i][0]表示A[..i]、B[..i]不交换A[i]、B[i]时的minSwap，
    //   dp[i][1]                  交换
    // 若A[i-1]<A[i] && B[i-1]<B[i]，
    //  交换第i-1项、也交换第i项：dp[i][1] = dp[i-1][1]+1
    //  不交换第i-1项、也不交换第i项：dp[i][0] = dp[i-1][0]
    // 若A[i-1]<B[i] && B[i-1]<A[i]，
    //  交换第i-i项、不交换第i项：dp[i][0] = dp[i-1][1]
    //  不交换第i-1项、交换第i项：dp[i][1] = dp[i-1][0]+1
    // 上述两种情况可同时存在。
    // 初始dp[0][0]=0, dp[0][1]=1
    // 递推式i这维只依赖i-1项，省掉i这维，i仍从左往右遍历
    const int N = A.size();
    vector<int> dp = {0, 1};
    for (int i = 1; i < N; i++) {
        vector<int> ndp = {INT_MAX, INT_MAX};
        if (A[i-1] < A[i] && B[i-1] < B[i]) {
            ndp[1] = min(ndp[1], dp[1] + 1);
            ndp[0] = min(ndp[0], dp[0]);
        }
        if (A[i-1] < B[i] && B[i-1] < A[i]) {
            ndp[0] = min(ndp[0], dp[1]);
            ndp[1] = min(ndp[1], dp[0] + 1);
        }
        swap(ndp, dp);
    }
    return min(dp[0], dp[1]);
}