801. Minimum Swaps To Make Sequences Increasing

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

两组数，允许同时在第i位swap，问最少swap几次使得它俩都是严格递增。minimum action问题不是BFS就是DP。action为swap or not, 取决于上位的值，上位的值分别来自于swap or not得到的值，因此需要维持两个状态，分别保存对当前位swap和keep的最优解。

解法参考了花花的。

/*
 * @lc app=leetcode id=801 lang=cpp
 *
 * [801] Minimum Swaps To Make Sequences Increasing
 */
class Solution {
public:
    int minSwap(vector<int>& A, vector<int>& B) {
        const int N = A.size();
        vector<int> keep(N, INT_MAX), swap(N, INT_MAX); 
        keep[0] = 0;
        swap[0] = 1;
        for (int i = 1; i < N; ++i) {
            if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
                keep[i] = keep[i - 1];
                // i和i-1都swap
                swap[i] = swap[i - 1] + 1;
            } 
            if (B[i] > A[i - 1] && A[i] > B[i - 1]) {
                // swap i
                swap[i] = min(swap[i], keep[i - 1] + 1); 
                // swap i - 1.
                keep[i] = min(keep[i], swap[i - 1]);
            }
        }
        return min(keep.back(), swap.back());
    }
};