线性动态规划：使序列递增的最小交换次数

题目描述
给定两个长度相等的整数数组 nums1 和 nums2。在一次操作中，你可以交换 nums1 和 nums2 中位于相同位置的元素。也就是说，交换 nums1[i] 和 nums2[i]。你的目标是使两个数组都变成严格递增的数组。你需要求出所需的最小交换次数。题目保证输入总是有效的，即总存在一种方式使得两个数组都严格递增。

示例
输入：nums1 = [1,3,5,4], nums2 = [1,2,3,7]
输出：1
解释：交换 nums1[3] 和 nums2[3] 后，数组变为 [1,3,5,7] 和 [1,2,3,4]，两者都是严格递增的。

解题过程

这个问题是一个典型的线性动态规划问题，我们需要逐个位置考虑，并记录在每个位置时，保持数组严格递增所需的最小交换次数，同时需要区分当前元素是否被交换。

1. 定义状态
   我们定义两个状态数组（或者两个状态变量，因为每个位置的状态只依赖于前一个位置的状态）：

   • keep[i]：表示使得位置 i 及之前的元素都满足严格递增条件，并且位置 i 的元素没有被交换时，所需的最小交换次数。
   • swap[i]：表示使得位置 i 及之前的元素都满足严格递增条件，并且位置 i 的元素被交换了时，所需的最小交换次数。

2. 寻找状态转移方程
   关键在于分析位置 i 和位置 i-1 的关系。对于位置 i 来说，能否保持严格递增，取决于 nums1 和 nums2 在 i 和 i-1 位置上的值是否满足特定的大小关系。我们需要考虑四种情况：

   • 情况 A： i-1 位置没交换，i 位置也没交换。
     有效条件为：
     nums1[i-1] < nums1[i] 且 nums2[i-1] < nums2[i]
     如果这个条件满足，那么 keep[i] 可以从 keep[i-1] 直接转移过来，因为 i 位置不需要交换，所以交换次数不变：keep[i] = min(keep[i], keep[i-1])。

   • 情况 B： i-1 位置交换了，i 位置没交换。
     有效条件为：
     nums2[i-1] < nums1[i] 且 nums1[i-1] < nums2[i] (注意，因为 i-1 位置交换了，所以原来 nums1[i-1] 的位置现在变成了 nums2[i-1]，原来 nums2[i-1] 的位置现在变成了 nums1[i-1])
     如果这个条件满足，那么 keep[i] 可以从 swap[i-1] 转移过来：keep[i] = min(keep[i], swap[i-1])。

   • 情况 C： i-1 位置没交换，i 位置交换了。
     有效条件为：
     nums1[i-1] < nums2[i] 且 nums2[i-1] < nums1[i]
     如果这个条件满足，那么 swap[i] 可以从 keep[i-1] 转移过来。因为 i 位置进行了一次交换，所以总交换次数要加1：swap[i] = min(swap[i], keep[i-1] + 1)。

   • 情况 D： i-1 位置交换了，i 位置也交换了。
     有效条件为：
     nums2[i-1] < nums2[i] 且 nums1[i-1] < nums1[i] (注意，因为两个位置都交换了，比较的是交换后的数组，即比较的是原 nums2 和原 nums1 的对应关系)
     如果这个条件满足，那么 swap[i] 可以从 swap[i-1] 转移过来。因为 i 位置进行了一次交换，所以总交换次数要加1：swap[i] = min(swap[i], swap[i-1] + 1)。

   综合以上四种情况，状态转移方程可以写为：

   keep[i] = 一个很大的数 (例如无穷大)
   swap[i] = 一个很大的数 (例如无穷大)
   
   if (nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i]) {
       keep[i] = min(keep[i], keep[i-1])   // 情况A
       swap[i] = min(swap[i], swap[i-1] + 1) // 情况D
   }
   if (nums1[i-1] < nums2[i] && nums2[i-1] < nums1[i]) {
       keep[i] = min(keep[i], swap[i-1])   // 情况B
       swap[i] = min(swap[i], keep[i-1] + 1) // 情况C
   }
   

3. 初始化
   对于第一个位置（i = 0）：

   • keep[0] = 0：第一个位置不交换，交换次数为0。
   • swap[0] = 1：第一个位置交换，交换次数为1。

4. 计算顺序
   从 i = 1 开始，遍历到数组的最后一个位置。

5. 最终结果
   遍历完整个数组后，最终的结果是 min(keep[n-1], swap[n-1])，其中 n 是数组的长度。这表示在最后一个位置，无论是交换还是不交换，只要能使整个数组严格递增，我们取其中交换次数最小的那个。

举例说明（使用示例）

数组：nums1 = [1, 3, 5, 4], nums2 = [1, 2, 3, 7]
n = 4

初始化：
i=0: keep[0] = 0, swap[0] = 1

处理 i=1 (比较位置0和位置1)：

• 情况A：nums1[0]=1 < nums1[1]=3 且 nums2[0]=1 < nums2[1]=2 -> 成立。
  keep[1] = min(INF, keep[0]=0) = 0
  swap[1] = min(INF, swap[0]+1=1+1=2) = 2
• 情况B/C：nums1[0]=1 < nums2[1]=2 且 nums2[0]=1 < nums1[1]=3 -> 成立。
  keep[1] = min(0, swap[0]=1) = 0
  swap[1] = min(2, keep[0]+1=0+1=1) = 1
  此时：keep[1] = 0, swap[1] = 1

处理 i=2 (比较位置1和位置2)：

• 情况A：nums1[1]=3 < nums1[2]=5 且 nums2[1]=2 < nums2[2]=3 -> 成立。
  keep[2] = min(INF, keep[1]=0) = 0
  swap[2] = min(INF, swap[1]+1=1+1=2) = 2
• 情况B/C：nums1[1]=3 < nums2[2]=3? -> 不成立 (3 < 3 不严格)。
  所以情况B/C不成立。
  此时：keep[2] = 0, swap[2] = 2

处理 i=3 (比较位置2和位置3)：

• 情况A：nums1[2]=5 < nums1[3]=4? -> 不成立。
  所以情况A/D不成立。
• 情况B/C：nums1[2]=5 < nums2[3]=7 且 nums2[2]=3 < nums1[3]=4 -> 成立。
  keep[3] = min(INF, swap[2]=2) = 2
  swap[3] = min(INF, keep[2]+1=0+1=1) = 1
  此时：keep[3] = 2, swap[3] = 1

最终结果：min(keep[3]=2, swap[3]=1) = 1，与示例输出一致。

这个动态规划解法的时间复杂度是 O(n)，空间复杂度通过使用两个变量（而不是两个数组）来记录前一个状态，可以优化到 O(1)。