教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册」题解库中对 LeetCode 0801「使序列递增的最小交换次数」Minimum Swaps to Make Sequences Increasing的完整讲解。题目标签为「数组、动态规划」难度为困难属于双数组线性动态规划的典型题目。读完本文你将掌握如何用二维状态dp[i][j]刻画「第 i 位换 / 不换」两种决策理解三种互斥情形下的状态转移方程并能够独立写出时间 O(n)、空间 O(n)可进一步压缩到 O(1)的 Python 解法。题目链接0801. 使序列递增的最小交换次数 - 力扣说明本题解在手册中的收录位置见 题解目录 - 0800-0899同时被归类于「数组、动态规划」分类下具体条目可参考 分类题单 中「双串线性 DP 问题」一节。题目大意给定两个长度相等的整型数组A和B。允许交换两个数组相同位置上的元素即把A[i]与B[i]互换可以交换任意多个位置但要求交换完成之后数组A与数组B都保持严格递增。要求返回使数组A和B保持严格递增状态所需的最小交换次数。题目保证给定的输入一定有效即一定存在至少一种合法交换方案。注意两个关键约束交换只能发生在同一下标i的A[i]与B[i]之间不能跨下标交换要求的是「严格递增」即A[i-1] A[i]且B[i-1] B[i]相等的情况不满足要求。示例演示示例 1输入A [1, 3, 5, 4]B [1, 2, 3, 7]输出1解释交换A[3]与B[3]即4与7互换得到A [1, 3, 5, 7]、B [1, 2, 3, 4]两数组均严格递增只需 1 次交换。解题思路二维状态动态规划本题属于线性动态规划中的双串线性 DP。按照 08_03_linear_dp_01.md 中线性 DP 的划分方式本题的输入是「两个数组」双串而每个下标位置只有「交换 / 不交换」两种离散决策因此非常适合用带决策维度的二维状态来建模。1. 状态定义对于两个数组的每一个位置iA[i]和B[i]只有两种情况换或不换。定义状态dp[i][j]dp[i][0]第i个位置的元素不交换保持原样时前i 1个位置所需的最小交换次数dp[i][1]第i个位置的元素交换A[i]与B[i]互换时前i 1个位置所需的最小交换次数。2. 初始条件边界当数组只有一个元素size 1时无论交换与否都能保证「严格递增」所以dp[0][0] 0第 0 个元素不做交换交换次数为 0dp[0][1] 1第 0 个元素做交换交换次数为 1。3. 状态转移相邻位置的关系如果有 2 个元素为了保证两个数组中的相邻元素都严格递增第 1 个元素是否交换与第 0 个元素直接相关推广到多个元素时第i个元素是否交换只与第i - 1个元素有关马尔可夫式相邻依赖。因此只需考察i与i - 1这两对相邻元素之间的关系。先按「原本数组当前是否满足递增关系」划分为两大类情形 A原本数组不满足递增关系即A[i - 1] A[i]或B[i - 1] B[i]。此时如果不做任何交换两个数组在位置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位不能交换否则两数组会同时被「拆散」。情形 B原本数组满足递增关系即A[i - 1] A[i]且B[i - 1] B[i]。此时原本已经满足递增还需要进一步考察两个数组交叉方向上相邻元素的关系因为一旦交换第i位新的A[i]来自原B[i]必须与新的B[i - 1]可能来自原A[i - 1]或原B[i - 1]保持严格递增。这里再细分为两种情况情况 B1交叉也满足递增即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情况 B2交叉不满足递增即A[i - 1] B[i]或B[i - 1] A[i]。 此时为了保证两个数组最终都严格递增第i位与第i - 1位的交换决策必须保持一致dp[i][0] dp[i - 1][0]第i位不交换则第i - 1位也不交换dp[i][1] dp[i - 1][1] 1第i位交换则第i - 1位也必须交换。至此三种互斥情形全部覆盖最终答案取最后一个位置两种状态下的较小值min(dp[size - 1][0], dp[size - 1][1])4. 转移方程速查表情形判定条件dp[i][0]dp[i][1]不满足递增必须交换A[i-1] A[i]或B[i-1] B[i]dp[i-1][1]dp[i-1][0] 1满足递增且交叉也递增A[i-1] A[i]、B[i-1] B[i]且A[i-1] B[i]、B[i-1] A[i]min(dp[i-1][0], dp[i-1][1])min(dp[i-1][0], dp[i-1][1]) 1满足递增但交叉不递增A[i-1] A[i]、B[i-1] B[i]且A[i-1] B[i]或B[i-1] A[i]dp[i-1][0]dp[i-1][1] 15. 解题代码对应原题解实现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])6. 复杂度分析时间复杂度O(n)。只需从第 1 位到第n - 1位遍历一次每步做常数次比较与转移总时间复杂度为O(n)其中n为数组长度。空间复杂度O(n)。使用了一个n × 2的二维数组保存状态本题解原实现中声明为size × size的矩阵实际只使用了两列。从代码结构可以看出每一步转移只依赖dp[i - 1][0]与dp[i - 1][1]两个值因此可以推断空间可进一步优化仅用两个变量keep不交换与swap交换滚动更新即可把空间复杂度降为O(1)这也是该题标准实现中最常用的写法。7. 滚动数组优化版本O(1) 空间class Solution: def minSwap(self, nums1: List[int], nums2: List[int]) - int: keep 0 # dp[i][0]当前位不交换 swap 1 # dp[i][1]当前位交换 for i in range(1, len(nums1)): if nums1[i - 1] nums1[i] and nums2[i - 1] nums2[i]: if nums1[i - 1] nums2[i] and nums2[i - 1] nums1[i]: keep, swap min(keep, swap), min(keep, swap) 1 else: keep, swap keep, swap 1 else: keep, swap swap, keep 1 return min(keep, swap)该版本与二维数组版本转移逻辑完全等价仅用两个变量代替整张表适用于面试中进一步追问空间复杂度的场景。举一反三从本题看双串线性 DP 的建模套路本题在「算法通关手册」的线性动态规划体系中属于双串输入、带决策维度的典型题目。与单串线性 DP如最长递增子序列中dp[i]表示以nums[i]结尾的解相比本题的核心差异在于决策离散且互斥每个位置只有「换 / 不换」两种选择因此状态天然拆成两维j 0 / 1相邻依赖局部性第i位的决策只影响且只受第i - 1位影响不需要枚举前面的所有位置这是本题能做到O(n)的关键交叉约束双数组问题必须同时检查「同向递增」与「交叉递增」两组条件缺一不可这也是本题容易写错的地方。建议读者在完成本题后回顾 动态规划基础 与 线性 DP 系列 章节将「决策维度状态」的思想与「买卖股票」系列同样使用dp[i][0/1]表示持股 / 空仓等题目对照学习可以更深刻地理解二维状态线性 DP 的通用模式。总结LeetCode 0801「使序列递增的最小交换次数」是一道质量很高的困难级动态规划题其核心价值在于用dp[i][j]把「是否交换」这一离散决策编码进状态通过分析相邻位置的三类关系不满足递增 / 交叉满足递增 / 交叉不满足递增推导出完备的状态转移方程在保证O(n)时间复杂度的同时可进一步把空间压缩到O(1)。掌握本题的建模思路后你不仅能独立解决这道困难题还能将其推广到其他「相邻约束 二元决策」类的双数组问题上。题解原始文档见 docs/solutions/0800-0899/minimum-swaps-to-make-sequences-increasing.md更多动态规划专题可参考 08_dynamic_programming 章节。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0674「最长连续递增序列」动态规划与滑动窗口双解法剖析AlgoNote 算法通关手册LeetCode 0674「最长连续递增序列」动态规划与滑动窗口双解法剖析 导读 本文是 AlgoNote「算法通关手册」对 L教程文档知识库AlgoNote 算法通关手册LeetCode 300「最长递增子序列」—— 从 O(n²) 动态规划到 O(n log n) 二分优化AlgoNote 算法通关手册LeetCode 300「最长递增子序列」—— 从 O n² 动态规划到 O n log n 二分优化 导读 本文基于 Algo教程文档知识库AlgoNote 题解LeetCode 0673 最长递增子序列的个数动态规划与线段树双解法AlgoNote 题解LeetCode 0673 最长递增子序列的个数动态规划与线段树双解法 导读 本题LeetCode 0673「最长递增子序列的个数」教程文档知识库上一篇终极指南如何高效使用Vercel AI SDK的generateText函数构建智能应用下一篇BitcoinCoreBrute常见问题解答解决使用中的10个关键问题创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考