题目链接：https://leetcode.cn/problems/minimum-swaps-to-make-sequences-increasing/
题目描述：
我们有两个长度相等且不为空的整型数组 nums1 和 nums2 。在一次操作中，我们可以交换 nums1[i] 和 nums2[i]的元素。
- 例如，如果
nums1 = [1,2,3,8]，nums2 =[5,6,7,4]，你可以交换i = 3处的元素，得到nums1 =[1,2,3,4]和nums2 =[5,6,7,8]。
返回 使 nums1 和 nums2 严格递增 所需操作的最小次数 。
数组 arr 严格递增 且 arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1] 。
注意：
- 用例保证可以实现操作。
示例 1:
输入: nums1 = [1,3,5,4], nums2 = [1,2,3,7]
输出: 1
解释:
交换 A[3] 和 B[3] 后，两个数组如下:
A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
两个数组均为严格递增的。
示例 2:
输入: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9]
输出: 1
提示:
2 <= nums1.length <= 105nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 2 * 105
解法：动态规划
由于题目用例可以保证交换之后，一定满足两个数组都是递增的。
我们使用dp[i][0] 和 dp[i][1] 来分别记录在第i位交换和不交换需要移动的最少次数。
那么在决定下标i是否交换时，我们可以针对nums1[i-1]、nums1[i]、nums2[i-1]、nums2[i]这四个值来判断那种方式比较合适，其实就只有几种情况了。
- 当两个数组在第i-1位和第i位本来就满足递增，并且交换后依然满足递增。即
nums1[i-1] < nums1[i]、nums2[i-1] < nums2[i]、nums1[i-1] < nums2[i]、nums2[i-1] < nums1[i]，同时满足上面四个条件时，针对第i位是否交换的两种情况：-
i选择【不交换】，则i-1可【互换】也可【不互换】，即dp[i][0] = Math.min(dp[i - 1][0], dp[i - 1][1])； -
i选择【交换】，则i-1可【互换】也可【不互换】，即dp[i][1] = dp[i][0] + 1。
-
- 当两个数组在第i-1位和第i位本来就满足递增，并且交换后不满足递增。即
nums1[i-1] < nums1[i]、nums2[i-1] < nums2[i]、nums1[i-1] > nums2[i]或者nums2[i-1] > nums1[i]，同时满足上面四个条件时，针对第i位是否交换的两种情况：-
i选择【不交换】，则i-1必须【不互换】，即dp[i][0] = dp[i - 1][0]； -
i选择【交换】，则i-1必须【互换】，即dp[i][1] = dp[i][1] + 1。
-
- 当两个数组在第i-1位和第i位一个递增，一个不递增或者两个都不递增，交换一个元素后，两个数组都递增。针对第i位是否交换的两种情况：
-
i选择【不交换】，则i-1必须【互换】，即dp[i][0] = dp[i - 1][1]； -
i选择【交换】，则i-1必须【不互换】，即dp[i][0] = dp[i - 1][0]；
-
在遍历结束后，会得到对应的状态值dp，最终结果为Math.min(dp[nums1.length - 1][0], dp[nums1.length - 1][1]。
代码：
class Solution {
public int minSwap(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length][2];
dp[0][0] = 0; dp[0][1] = 1;
for (int i = 1; i < nums1.length; i++) {
int a1 = nums1[i - 1], a2 = nums1[i], b1 = nums2[i - 1], b2 = nums2[i];
if ((a1 < a2 && b1 < b2) && (b1 < a2 && a1 < b2)) {
dp[i][0] = Math.min(dp[i - 1][0], dp[i - 1][1]); // 如果i【不互换】，则i-1可【互换】也可【不互换】
dp[i][1] = dp[i][0] + 1; // 如果i【互换】，则i-1可【互换】也可【不互换】
} else if (a1 < a2 && b1 < b2) {
dp[i][0] = dp[i - 1][0]; // 如果i【不互换】，则i-1必须【不互换】
dp[i][1] = dp[i - 1][1] + 1; // 如果i【互换】，则i-1必须【互换】
} else {
dp[i][0] = dp[i - 1][1]; // 如果i【不互换】，则i-1必须【互换】
dp[i][1] = dp[i - 1][0] + 1; // 如果i【互换】，则i-1必须【不互换】
}
}
return Math.min(dp[nums1.length - 1][0], dp[nums1.length - 1][1]);
}
}
