[数据结构与算法]【LeetCode成长系列（动态规划状态机DP困难题）】801. 使序列递增的最小交换次数

??前面的话??

本篇文章介绍一道动态规划状态机DP困难题【801. 使序列递增的最小交换次数】题解，难度为：困难 标签：动态规划 多状态（状态机DP）

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏??留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年10月11日🌴
??坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

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

🔐题目详情

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

难度困难

我们有两个长度相等且不为空的整型数组 nums1 和 nums2 。在一次操作中，我们可以交换 nums1[i] 和 nums2[i]的元素。

• 例如，如果 nums1 = [1,2,3,8] ， nums2 =[5,6,7,4] ，你可以交换 i = 3 处的元素，得到 nums1 =[1,2,3,4] 和 nums2 =[5,6,7,8] 。

返回 使 nums1 和 nums2 严格递增 所需操作的最小次数 。

数组 arr 严格递增 且 arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1] 。

注意：

• 用例保证可以实现操作。

示例 1:

输入: nums1 = [1,3,5,4], nums2 = [1,2,3,7]
输出: 1
解释: 
交换 A[3] 和 B[3] 后，两个数组如下:
A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
两个数组均为严格递增的。

示例 2:

输入: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9]
输出: 1

提示:

• 2 <= nums1.length <= 105
• nums2.length == nums1.length
• 0 <= nums1[i], nums2[i] <= 2 * 105

💡解题思路

基本思路： 动态规划

解题思路：
状态机DP（两个状态），状态机DP本质上就是包含多个待选状态，不同的状态之间有相互转化的方法，借助这些转化的手段，达成状态之间的相互转移。

本题采用双状态动态规划即可解决，首先题目要求的就是将两个数组相同下标的元素进行交换，所以我们仅需要考虑交换前后数组元素大小的关系即可。

状态定义： $dp[i][j]$ 表示$[0,i]$下标内数组最小交换次数，其中$j$表示状态，$0$表示不交换，$1$表示交换。

确定初始状态： $dp[0][0]=0,dp[0][1]=1$, 其他状态置为$dp[i][0]=dp[i][1]=n+1$（交换次数最多为$n$）。

状态转移方程：
由于是在相同位置进行交换 ，满足交换后变为有序的情况只有两种，一种原来两个数组对应的两个连续的数就是递增的，即满足nums1[i]>nums1[i-1] && nums2[i]>nums2[i-1]
此时你可以交换，但是$i$ 与 $i?1$ 位置都得交换 $dp[i][1]=dp[i?1][1]+1$
也可以不交换，但是 $i$ 与 $i?1$ 位置都得不交换 $dp[i][0]=dp[i?1][0]$。

即：
$$dp[i][1]=dp[i?1][1]+1，dp[i][0]=dp[i?1][0]$$

另外一种情况就是：第一个数组后一个元素大于第二个数组前一个元素，第二个数组后一个元素大于第一个数组前一个元素，即 nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]。

此时交换$i$位置元素 或者交换$i?1$位置元素，由于该情况可能与上一种情况同时出现，所以我们取两者较小值。

$i$位置交换 $dp[i][1]=min(dp[i][1],dp[i?1][0]+1)$
$i?1$位置交换 $dp[i][0]=min(dp[i][0],dp[i?1][1])$

最终较小交换次数为两个状态中较小的值，即$min(dp[n?1][0],dp[n?1][1])$

滚动数组优化：
我们发现第i行的两个状态依赖于第i-1的两个状态，就是第i行仅依赖于上一行，即i-1行，所以我们可以使用滚动数组进行优化。

为了防止污染第i行的状态（因为第i+1行需要用到），我们先使用a变量来表示当前第i行不交换的状态，使用b变量来表示当前第i行交换的状态，初始值都为n+1，由于只有两行数组表示前后两组状态，我们使用滚动的形式进行状态更新切换，即奇偶行，对i按位与1即可，不妨记$cur=i\&1,pre=(i?1)\&1$。

满足nums1[i]>nums1[i-1] && nums2[i]>nums2[i-1]
此时你可以交换，但是$i$ 与 $i?1$ 位置都得交换 $b=dp[pre][1]+1$
也可以不交换，但是 $i$ 与 $i?1$ 位置都得不交换 $a=dp[pre][0]$。

满足nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]。

此时交换$i$位置元素 或者交换$i?1$位置元素，由于该情况可能与上一种情况同时出现，所以我们取两者较小值。

$i$位置交换 $b=min(b,dp[pre][0]+1)$
$i?1$位置交换 $a=min(a,dp[pre][1])$

最后再正式更新第i行状态的值$dp[cur][0]=a,dp[cur][1]=b$。

最终最小交换次数为交换与不交换状态较小的值$min(dp[(n?1)\&1][0],dp[(n?1)\&1][1])$。

🔑源代码

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        //听说这种dp叫做状态机
        //状态定义：dp[i][j] 表示[0,i]下标内数组最小交换次数，其中j表示状态，0表示不交换，1表示交换
        //初始状态：dp[0][0] = 0 dp[0][1] = 1, 其他状态置为dp[i][0] = dp[i][1] = n + 1（交换次数最多为n）
        //转移方程：由于是在相同位置进行交换 
        //满足交换后变为有序的情况只有两种，一种原来两个数组对应的两个连续的数就是递增的
        //即满足nums1[i]>nums1[i-1] nums2[i]>nums2[i-1]
        //此时你可以交换 但是i 与 i-1 位置都得交换 dp[i][1] = dp[i-1][1] + 1
        //也可以不交换 但是 i 与 i-1 位置都得不交换 dp[i][0] = dp[i-1][0]

        //另外一种情况就是：第一个数组后一个元素大于第二个数组前一个元素，第二个数组后一个元素大于第一个数组前一个元素
        //即 nums1[i] > nums2[i-1] nums2[i] > nums1[i-1]
        //此时交换i位置元素 或者 i-1位置元素交换
        //i位置交换 dp[i][1] = min(dp[i][1], dp[i-1][0] + 1)
        //i - 1位置交换 dp[i][0] = min(dp[i][0], dp[i-1][1])
        int n = nums1.length;
        int[][] dp = new int[n][2];

        // 初始
        dp[0][1] = 1;
        for (int i = 1; i < n; i++) dp[i][1] = dp[i][0] = n + 1;

        // 状态转移
        for (int i = 1; i < n; i++) {
            // 情况1
            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = dp[i - 1][1] + 1;
            }
            // 情况2
            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
                dp[i][0] = Math.min(dp[i][0], dp[i - 1][1]);
                dp[i][1] = Math.min(dp[i][1], dp[i - 1][0] + 1);
            }
        }
        return Math.min(dp[n - 1][0], dp[n - 1][1]);
    }
}

滚动数组优化：

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        //听说这种dp叫做状态机
        //状态定义：dp[i][j] 表示[0,i]下标内数组最小交换次数，其中j表示状态，0表示不交换，1表示交换
        //初始状态：dp[0][0] = 0 dp[0][1] = 1, 其他状态置为dp[i][0] = dp[i][1] = n + 1（交换次数最多为n）
        //转移方程：由于是在相同位置进行交换 
        //满足交换后变为有序的情况只有两种，一种原来两个数组对应的两个连续的数就是递增的
        //即满足nums1[i]>nums1[i-1] nums2[i]>nums2[i-1]
        //此时你可以交换 但是i 与 i-1 位置都得交换 dp[i][1] = dp[i-1][1] + 1
        //也可以不交换 但是 i 与 i-1 位置都得不交换 dp[i][0] = dp[i-1][0]

        //另外一种情况就是：第一个数组后一个元素大于第二个数组前一个元素，第二个数组后一个元素大于第一个数组前一个元素
        //即 nums1[i] > nums2[i-1] nums2[i] > nums1[i-1]
        //此时交换i位置元素 或者 i-1位置元素交换
        //i位置交换 dp[i][1] = min(dp[i][1], dp[i-1][0] + 1)
        //i - 1位置交换 dp[i][0] = min(dp[i][0], dp[i-1][1])
        int n = nums1.length;
        int[][] dp = new int[2][2];

        // 初始
        dp[0][1] = 1;
        dp[1][1] = n + 1;
        dp[1][0] = n + 1;

        // 状态转移
        for (int i = 1; i < n; i++) {
            int pre = (i - 1) & 1;
            int cur = i & 1;
            int a = n + 1;
            int b = n + 1;
            // 情况1
            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
                a = dp[pre][0];
                b = dp[pre][1] + 1;
            }
            // 情况2
            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
                a = Math.min(a, dp[pre][1]);
                b = Math.min(b, dp[pre][0] + 1);
            }
            dp[cur][0] = a;
            dp[cur][1] = b;
        }
        return Math.min(dp[(n - 1) & 1][0], dp[(n - 1) & 1][1]);
    }
}

🌱总结

本题为动态规划双状态运用题，状态转移的过程中【交换】状态需要利用到【非交换状态】，通过两个状态数组相互转移，达到状态转移的目的。