题目形容

办法 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]);
    }
}