本文共 2060 字，大约阅读时间需要 6 分钟。

我们有两个长度相等且不为空的整型数组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]区间内的整数。

解题思路

这个问题不难想到动态规划，我们有两个状态，一种是交换位置i的元素，设此时总的最少交换次数是$f_1(i)$，另一种是不交换位置i的元素，设此时总的最少交换次数是$f_2(i)$。如果此时A[i-1]<A[i] && B[i-1]<B[i] && A[i-1]<B[i] && B[i-1]<A[i]，那么此时

• $f_1(i)=min(f_1(i-1),f_2(i-1))$
• $f_2(i)=min(f_1(i-1),f_2(i-1))+1$

也就是此时i-1位置可以交换，也可以不交换。如果此时仅仅A[i-1]<A[i] && B[i-1]<B[i]，那么

• $f_1(i)=f_1(i-1)$
• $f_2(i)=f_2(i-1)+1$

如果位置i-1交换，那么为了保证不等式成立，位置i也要交换。同理，如果位置i-1不交换，那么位置i也就不用交换。如果此时仅仅A[i-1]<B[i] && B[i-1]<A[i]，那么

• $f_1(i)=f_2(i-1)$
• $f_2(i)=f_1(i-1)+1$

如果位置i-1交换，那么为了保证不等式成立，位置i不能交换。同理，如果位置i-1不交换，那么位置i需要交换。

最后思考边界条件，当字符串是1的时候，如果不交换，那么返回0；如果交换，那么返回1。最后我们只需返回$f_1(len(str))$和$f_2(len(str))$。在写代码的时候，由于只有两种状态，所以我们只需要两个变量存最后结果即可，而不需要开辟一个数组。

class Solution:    def minSwap(self, A: List[int], B: List[int]) -> int:        n, f1, f2 = len(A), 0, 1        for i in range(1, n):            s1 = A[i - 1] < A[i] and B[i - 1] < B[i]             s2 = A[i - 1] < B[i] and B[i - 1] < A[i]            if s1 and s2:                f1, f2 = min(f1, f2), min(f1, f2) + 1            elif s1:                f2 += 1             else:                 f1, f2 = f2, f1 + 1        return min(f1, f2)

reference:

https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/discuss/161887/Bottom-up-DP-with-Optimization-(Java-Python)

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/100587859 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！