最近面了某外包，真真切切感受到外包公司的恶意。。

今天咱们聊一个有点烧脑的算法题：使序列递增的最小交换次数。

题目是这样的：给你两个长度相同的数组 nums1 和 nums2，它们一开始分别是乱序的。你可以选择在任意位置交换 nums1[i] 和 nums2[i] 的值，也可以不交换。最终目标是让这两个数组都严格递增，并求出最少需要的交换次数。

示例：

nums1 = {1, 3, 5, 4};
nums2 = {1, 2, 3, 7};

通过操作可以让这两个数组变成递增：

• 交换 nums1[3] 和 nums2[3] 后，得到：

  nums1 = {1, 3, 5, 7};
  nums2 = {1, 2, 3, 4};
  

结果：只需要一次交换。

这道题的思路是动态规划（DP），分两种状态讨论：

1. 不交换当前元素（保持原样）。
2. 交换当前元素（把当前的 nums1[i] 和 nums2[i] 交换）。

为了实现这个，我们定义两个数组：

• keep[i]：表示让前 i 个元素递增，且第 i 个元素保持不交换的最小交换次数。
• swap[i]：表示让前 i 个元素递增，且第 i 个元素交换的最小交换次数。

状态转移方程：

1. 如果前一组 (nums1[i-1] 和 nums2[i-1]) 和当前组本身都满足递增（即 nums1[i-1] < nums1[i] 且 nums2[i-1] < nums2[i]），那么：

• 当前不交换：keep[i] = keep[i-1]。
• 当前交换：swap[i] = swap[i-1] + 1（因为交换了当前）。

• 当前不交换：keep[i] = Math.min(keep[i], swap[i-1])。
• 当前交换：swap[i] = Math.min(swap[i], keep[i-1] + 1)。

代码实现：

public class MinSwapToMakeSequencesIncreasing {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] keep = new int[n];
        int[] swap = new int[n];
                // 初始状态：第一个元素不交换和交换的代价
        keep[0] = 0;
        swap[0] = 1;
        for (int i = 1; i < n; i++) {
            // 初始化为最大值
            keep[i] = swap[i] = Integer.MAX_VALUE;
            // 情况 1：保持 nums1[i-1] < nums1[i] 且 nums2[i-1] < nums2[i]
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                keep[i] = keep[i - 1];  // 当前不交换
                swap[i] = swap[i - 1] + 1;  // 当前交换
            }
            // 情况 2：交叉递增 nums1[i-1] < nums2[i] 且 nums2[i-1] < nums1[i]
            if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
                keep[i] = Math.min(keep[i], swap[i - 1]);  // 继承之前交换的状态
                swap[i] = Math.min(swap[i], keep[i - 1] + 1);  // 当前交换
            }
        }
        // 返回两种状态中最小的代价
        return Math.min(keep[n - 1], swap[n - 1]);
    }
    public static void main(String[] args) {
        MinSwapToMakeSequencesIncreasing solution = new MinSwapToMakeSequencesIncreasing();
        int[] nums1 = {1, 3, 5, 4};
        int[] nums2 = {1, 2, 3, 7};
        System.out.println("最小交换次数: " + solution.minSwap(nums1, nums2));  // 输出：1
    }
}

运行逻辑：

1. 第一个元素不需要特殊处理，直接初始化：keep[0] = 0, swap[0] = 1。
2. 从第二个元素开始，判断是否满足递增条件：

• 如果直接递增，继续延续前面的状态。
• 如果交叉递增，尝试交换状态。

写这题的时候，我脑海里冒出了一个画面：两个数组手拉手，一个说“你别动”，另一个说“那我动吧”，然后一拍即合递增了。这种默契要是放在代码里，就是动态规划的优雅体现。你看，算法里不光有逻辑，还有点“爱情的味道”！