# 801. Minimum Swaps To Make Sequences Increasing

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

解法参考了花花的。

```cpp
/*
 * @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());
    }
};


```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/duo-zhuang-tai-dp/801.-minimum-swaps-to-make-sequences-increasing.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.