leetcode 801

问题

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.

1
2
3
4
5
6
7
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].

分析

对于每个 $i$ ，都有两种可能的操作，一种操作是交换 $A[i], B[i]$ ，另一种操作是不交换 $A[i], B[i]$。因此，我们使用 $dp[i][0]$ 来表示，在 $i$ 时不交换，且维护两个数列严格增所需要的最小交换数。 $dp[i][1]$ 来表示，在 $i$ 时交换，且维护两个数列严格增所需要的最小交换数。则有状态转移如代码所示。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minSwap(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> dp(2), dp2;
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 1; i < n; ++i) {
            dp2 = dp;
            dp  = {0x3f3f3f3f, 0x3f3f3f3f};
            if (A[i-1]<A[i] && B[i-1]<B[i]) {
                dp[0] = min(dp[0], dp2[0]);
                dp[1] = min(dp[1], dp2[1]);
            }
            if (A[i-1]<B[i] && B[i-1]<A[i]) {
                dp[0] = min(dp[0], dp2[1]);
                dp[1] = min(dp[1], dp2[0]);
            }
            dp[1] += 1;
        }
        return min(dp[0], dp[1]);
    }
};