AlgoPressAppearance
0801-使序列递增的最小交换次数
题目描述
https://leetcode.cn/problems/minimum-swaps-to-make-sequences-increasing
我们有两个长度相等且不为空的整型数组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
思路 : 动态规划 TODO 复习
csharp
public class Solution {
public int MinSwap(int[] nums1, int[] nums2) {
int n = nums1.Length;
int[,] dp = new int[n,2]; //dp[i,0] 不交换, dp[i,1] 交换
dp[0,0] = 0;
dp[0,1] = 1;
//0,4,4,5,9
//0,1,6,8,10
for(int i=1; i < n; i++){
dp[i,0] = n;
dp[i,1] = n;
if(nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]){
dp[i,0] = Math.Min(dp[i,0],dp[i-1,0]);
dp[i,1] = Math.Min(dp[i,1],dp[i-1,1]+1);
}
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]);
}
}