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

• 标签：数组、动态规划
• 难度：困难

题目链接

• 0801. 使序列递增的最小交换次数 - 力扣

题目大意

给定两个长度相等的整形数组 A 和 B。可以交换两个数组相同位置上的元素，比如 A[i] 与 B[i] 交换，可以交换多个位置，但要保证交换之后保证数组 A和数组 B 是严格递增的。

要求：返回使得数组 A和数组 B 保持严格递增状态的最小交换次数。假设给定的输入一定有效。

解题思路

可以用动态规划来做。

对于两个数组每一个位置上的元素 A[i] 和 B[i] 来说，只有两种情况：换或者不换。

动态规划的状态 dp[i][j] 表示为：第 i 个位置元素，不交换（j = 0）、交换（j = 1）状态时的最小交换次数。

如果数组元素个数只有一个，则：

• dp[0][0] = 0 ，第 0 个元素不做交换，交换次数为 0。
• dp[0][1] = 1，第 0 个元素做交换，交换次数为 1。

如果有 2 个元素，为了保证两个数组中的相邻元素都为递增元素，则第 2 个元素交换与否与第 1 个元素有关。同理如果有多个元素，那么第 i 个元素交换与否，只与第 i - 1 个元素有关。现在来考虑第 i 个元素与第 i - 1 的元素的情况。

先按原本数组当前是否满足递增关系来划分，可以划分为：

• 原本数组都满足递增关系，即 A[i - 1] < A[i] 并且 B[i - 1] < B[i]。
• 不满足上述递增关系的情况，即 A[i - 1] >= A[i] 或者 B[i - 1] >= B[i]。

可以看出，不满足递增关系的情况下是肯定要交换的。只需要考虑交换第 i 位元素，还是第 i - 1 位元素。

• dp[i][0] = dp[i - 1][1]，第 i 位若不交换，则第 i - 1 位必须交换。
• dp[i][1] = dp[i - 1][0] + 1，第 i 位交换，则第 i - 1 位不能交换。

下面再来考虑原本数组都满足递增关系的情况。考虑两个数组间相邻元素的关系。

• A[i - 1] < B[i] 并且 B[i - 1] < A[i]。
• A[i - 1] >= B[i] 或者 B[i - 1] >= A[i]。

如果是 A[i - 1] < B[i] 并且 B[i - 1] < A[i] 情况下，第 i 位交换，与第 i - 1 位交换与否无关，则 dp[i][j] 只需取 dp[i-1][j] 上较小结果进行计算即可，即：

• dp[i][0] = min(dp[i-1][0], dp[i-1][1])
• dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1

如果是 A[i - 1] >= B[i] 或者 B[i - 1] >= A[i] 情况下，则如果第 i 位交换，则第 i - 1 位必须跟着交换。如果第 i 位不交换，则第 i - 1 为也不能交换，即：

• dp[i][0] = dp[i - 1][0]，如果第 i 位不交换，则第 i - 1 位也不交换。
• dp[i][1] = dp[i - 1][1] + 1，如果第 i 位交换，则第 i - 1 位也必须交换。

这样就考虑了所有的情况，最终返回最后一个元素，（交换、不交换）状态下的最小值即可。

代码

class Solution:
    def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
        size = len(nums1)
        dp = [[0 for _ in range(size)] for _ in range(size)]
        dp[0][1] = 1
        for i in range(1, size):
            if nums1[i - 1] < nums1[i] and nums2[i - 1] < nums2[i]:
                if nums1[i - 1] < nums2[i] and nums2[i - 1] < nums1[i]:
                    # 第 i 位交换，与第 i - 1 位交换与否无关
                    dp[i][0] = min(dp[i-1][0], dp[i-1][1])
                    dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1
                else:
                    # 如果第 i 位不交换，则第 i - 1 位也不交换
                    # 如果第 i 位交换，则第 i - 1 位也必须交换
                    dp[i][0] = dp[i - 1][0]
                    dp[i][1] = dp[i - 1][1] + 1
            else:
                dp[i][0] = dp[i - 1][1]         # 如果第 i 位若不交换，则第 i - 1 位必须交换
                dp[i][1] = dp[i - 1][0] + 1     # 如果第 i 位交换，则第 i - 1 位不能交换
        return min(dp[size - 1][0], dp[size - 1][1])