题目形容
办法1 动静布局
说一下底层逻辑吧，这道题的状态转移方程还是比拟有意思的，对于我来说不太好想。您也能够间接跳过错解的剖析，间接转到正解局部浏览
原始版本(谬误示例)
不晓得读者在做这道题的时候会不会跟我一样，我在最后的计划只思考A[i]>A[i-1] && B[i]>B[i-1]这个条件，满足则不替换i地位元素，否则则替换；这种计划还是比拟奢侈的，而后思考的条件其实并不全面，咱们一会举个例子解释一下；这里先看一下这个版本的代码
// 75 / 102 个通过测试用例class Solution { public int minSwap(int[] A, int[] B) { int[] dp = new int[A.length]; dp[0] = 0; for(int i = 1;i<A.length;i++){ if(A[i]>A[i-1] && B[i]>B[i-1]){ dp[i] = dp[i-1]; }else{ int t = A[i]; A[i] = B[i]; B[i] = t; dp[i] = dp[i-1] + 1; } } return dp[A.length - 1]; }}这个版本谬误在哪呢，举个例子来说：
A = [0,4,4,5,9]B = [0,1,6,8,10]
按这个版本代码的逻辑 在遍历到i=2时 判断到A[i]>A[i-1] //A[2]=4 > A[1]=4不成立，所以进行了一次A[2]和B[2]的替换后，A=[0,4,6,5,9],B=[0,1,4,8,10],同样的遍历i=3时因为A[3]=5 < A[2]=6也会进行一次替换，所以总共替换了2次；
但实际上，咱们会发现在这个例子中，咱们能够间接替换i=1地位达到目标
所以实际上是因为咱们的状态转移条件和方程都思考的不充沛导致这种漏解的景象，其实在这里咱们能够感知到一点突破口了，在某些状况下，咱们能够抉择替换i地位，也能够抉择替换i-1地位！，
改过后的版本
首先题目保障了所有的输出用例都是无效的，也就是说肯定存在某种替换办法能够使得A[i] 、B[i]最终严格递增，因而对于任意地位i，必然满足以下3种状况：
1、A[i]>A[i-1] && B[i] > B[i-1]
2、A[i]>B[i-1] && B[i] > A[i-1]
3、同时满足条件1和2
条件2能够简略了解成i地位替换后 能够实现{i-1,i}序列的无序到有序
例如A=[3,2],B=[1,4]就是满足条件2的一个例子~
(也就是说咱们满足条件1时排除掉条件2，满足条件2时排除条件1，条件3为同时满足)
所以有状态转移方程如下：
满足条件1(部分序列有序)：
- 替换i时必须同时替换i-1
- 不替换i时也必须同时不替换i-1
满足条件2(部分序列无序，替换1次可变为有序)：
- 只替换i并且不替换i-1
- 只替换i-1并且不替换i
满足条件3：
- 替换i地位，i-1能够抉择替换或不替换，抉择最优状况
- 不替换i地位，i-1能够抉择替换或不替换，抉择最优状况
这里给条件1和条件2的例子 供读者本人领会
条件1：A=[1,4,8,5],B=[4,7,6,9]
条件2：A=[1,4,6,5],B=[4,7,8,9]
有了状态转移方程，剩下的看代码就能够了，要害局部已正文
class Solution { public int minSwap(int[] A, int[] B) { int n = A.length; //keep[i]示意不替换i的状况下 使得0~i有序的最小替换次数 int[] keep = new int[n]; //swap[i]示意替换i的状况下 使得0~i有序的最小替换次数 int[] swap = new int[n]; keep[0] = 0; swap[0] = 1; for(int i = 1;i<n;i++){ // 满足条件3 if((A[i]>A[i-1]&&B[i]>B[i-1])&&(A[i]>B[i-1]&&B[i]>A[i-1])){ // i不替换，i-1能够替换也能够不替换 择优抉择 keep[i] = Math.min(keep[i-1],swap[i-1]); // i 替换，i-1能够替换也能够不替换 择优抉择 swap[i] = Math.min(keep[i-1],swap[i-1]) + 1; }else if(A[i] > A[i-1] && B[i] > B[i-1]){ // 满足条件1的状况下(部分有序） // 必须同时替换或同时不替换以保障部分有序 // i不替换，i-1也不替换 keep[i] = keep[i-1]; // i替换，i-1也替换 swap[i] = swap[i-1] + 1; }else{ // 部分无序 i、i-1中只有一个地位替换 // i不替换，替换i-1 keep[i] = swap[i-1]; // i替换，不替换i-1 swap[i] = keep[i-1] + 1; } } //择优抉择 return Math.min(keep[n-1],swap[n-1]); }}