题目来源：801. 使序列递增的最小交换次数

题目描述：我们有两个长度相等且不为空的整型数组 A 和 B 。

我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。

在交换过一些元素之后，数组 A 和 B 都应该是严格递增的（数组严格递增的条件仅为A[0] < A[1] < A[2] < ... < A[A.length - 1]）。

给定数组 A 和 B ，请返回使得两个数组均保持严格递增状态的最小交换次数。假设给定的输入总是有效的。

思路：

设d[i][0]表示到元素i时，不交换A[i],B[i]的最小交换次数

设d[i][1]表示到元素i时，交换A[i],B[i]的最小交换次数

动态规划

每个位置是否需要交换，依赖前一个位置的结果

考虑三种情况

1. 第一种：两组数组有序，且存在交叉
   1. 当前位置可以选择交换，也可以不选择交换
2. 第二种：两组数组有序，且不存在交叉
   1. 当前位置i选择交换，i-1这个位置必须交换
   2. 当前位置i选择不交换，i-1这个位置也不能交换
3. 第三种：其中一组数组无序
   1. 当前位置i选择交换，i-1这个位置就不能交换
   2. 当前位置i选择不交换，i-1这个位置就必须选择交换

在有序的情况下，交叉是指，在当前位置i下，存在a[i-1] < b[i] 且 b[i-1] < a[i]

例：

默认当前位置i从1开始

1. 第一种：a={2,5}, b={3,6}
2. 第二种：a={2,4}, b={5,7}
3. 第三种：a={6,4}, b={3,7}

最后的结果就是比较d[i][0]和d[i][1]哪个交换的次数最小就好了。

代码：

class Solution {
    public int minSwap(int[] a, int[] b) {
        int len = a.length;
        int[] keep = new int[len];
        int[] swap = new int[len];
        Arrays.fill(keep, Integer.MAX_VALUE);	// 初始化
        Arrays.fill(swap, Integer.MAX_VALUE);
        keep[0] = 0;	// 初始状态
        swap[0] = 1;
        for(int i = 1;i<len;i++){
            if((a[i] > a[i-1] && b[i] > b[i-1]) && (a[i] > b[i-1] && b[i] > a[i-1]))
            {
                // 第一种情况
                keep[i] = Math.min(keep[i-1], swap[i-1]);
                swap[i] = Math.min(swap[i-1], keep[i-1]) + 1;
                continue;
            }
            if(a[i] > a[i-1] && b[i] > b[i-1])
            {
                // 第二种情况
                keep[i] = keep[i-1];
                swap[i] = swap[i-1] + 1;
                continue;
            }
            if(a[i] > b[i-1] && b[i] > a[i-1])
            {
                // 第三种情况
                keep[i] = swap[i-1];
                swap[i] = keep[i-1] + 1;
                continue;
            }
        }
        return Math.min(keep[len-1], swap[len-1]);
    }
}