# 801     Minimum Swaps To Make Sequences Increasing

## 801. [Minimum Swaps To Make Sequences Increasing](https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/description/)

## 1. Question

We have two integer sequences`A`and`B`of the same non-zero length.

We are allowed to swap elements`A[i]`and`B[i]`. Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps,`A`and`B`are both strictly increasing. (A sequence is\_strictly increasing\_if and only if`A[0] < A[1] < A[2] < ... < A[A.length - 1]`.)

Given A and B, return the minimum number of swaps to make both sequences strictly increasing. It is guaranteed that the given input always makes it possible.

```
Example:
Input: A = [1,3,5,4], B = [1,2,3,7]

Output: 1

Explanation: 
Swap A[3] and B[3].  Then the sequences are:
A = [1, 3, 5, 7] and B = [1, 2, 3, 4]
which are both strictly increasing.
```

**Note:**

* `A, B`are arrays with the same length, and that length will be in the range`[1, 1000]`.
* `A[i], B[i]`are integer values in the range`[0, 2000]`.

## 2. Implementation

**(1) DP**

思路: 对于数组上的每个位置我们只有两种操作: swap, no swap。所以我们建立一个2二维数组dp, dp\[i]\[0]表示我们不在第i个位置swap, dp\[i]\[1]表示在第i个位置swap

有以下几种情况影响我们的状态转移方程:

1.如果A\[i - 1] < A\[i] && B\[i - 1] < B\[i] && A\[i - 1] < B\[i] && B\[i - 1] < A\[i], 这个时候我们在第i个位置既可以swap也可以不swap

1. 如果A\[i - 1] < A\[i] && B\[i - 1] < B\[i] && (A\[i - 1] > B\[i] || B\[i - 1] > A\[i]), 这个时候我们在第i个位置的操作和第i - 1个位置的操作必须一致
2. 如果(A\[i - 1] > A\[i] || B\[i - 1] > B\[i]) && (A\[i - 1] < B\[i] && B\[i - 1] < A\[i]), 这个时候在第i个位置的操作和在第i - 1个位置的操作相反

```java
class Solution {
    public int minSwap(int[] A, int[] B) {
        int n = A.length;
        int[][] dp = new int[n][2];
        // dp[i][0] means we don't swap at ith position
        // dp[i][1] means we swap at ith position
        dp[0][0] = 0;
        dp[0][1] = 1;

        for (int i = 1; i < n; i++) {
            // Case 1: In this case we can either swap or stay the same at ith poition
            if (A[i - 1] < A[i] && B[i - 1] < B[i] && A[i - 1] < B[i] && B[i - 1] < A[i]) {
                dp[i][0] = Math.min(dp[i - 1][0], dp[i - 1][1]);
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;
            }
            // Case 2: If we swap at (i - 1)th position, we should swap at ith position
            // If we don't sway at (i - 1)th position, we keep the same operation at ith position
            else if (A[i - 1] < A[i] && B[i - 1] < B[i]) {
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = dp[i - 1][1] + 1;
            }
            // Case 3: If we swap at (i - 1)th position, we don't swap at ith position
            // If we don't swap at (i - 1)th position, we swap at ith position
            else {
                dp[i][0] = dp[i - 1][1];
                dp[i][1] = dp[i - 1][0] + 1;
            }
        }
        return Math.min(dp[n - 1][0], dp[n - 1][1]);
    }
}
```

## 3. Time & Space Complexity

**DP:** 时间复杂度O(n), 空间复杂度O(n)


---

# 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://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/801-minimum-swapsto-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.