801. 使序列递增的最小交换次数

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

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

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

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

示例:
输入: A = [1,3,5,4], B = [1,2,3,7]
输出: 1
解释: 
交换 A[3] 和 B[3] 后，两个数组如下:
A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
两个数组均为严格递增的。

注意:

• A, B 两个数组的长度总是相等的，且长度的范围为 [1, 1000]。
• A[i], B[i] 均为 [0, 2000]区间内的整数。

解法：（dp）

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var minSwap = function(nums1, nums2) {
  let n = nums1.length;
  //changeArr[i] 表示第i个元素交换时交换了的次数
  let changeArr = new Array(n).fill(Infinity);
  //nochangeArr[i] 表示第i个元素没有交换时交换了的次数
  let nochangeArr = new Array(n).fill(Infinity);
  changeArr[0] = 1;
  nochangeArr[0] = 0;
  for(let i=1;i<n;i++){
    //两个条件
    //nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]
    //nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]
    //都满足时 i-1位置可换  i位置也可换
    if(nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1] && (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1])){
      changeArr[i] = Math.min(changeArr[i-1],nochangeArr[i-1]) + 1;
      nochangeArr[i] = Math.min(changeArr[i-1],nochangeArr[i-1]);
      continue;
    }
    
    //只满足 nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1] 
    if(nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]){
      changeArr[i] = changeArr[i-1] + 1;
      nochangeArr[i] = nochangeArr[i-1];
    }
    
    //只满足nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]
    if(nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]){
      changeArr[i] = nochangeArr[i-1] + 1;
      nochangeArr[i] = changeArr[i-1];
    }
  }
  return Math.min(changeArr[i-1],nochangeArr[i-1]);
}