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

素颜马尾好姑娘i 2023-07-02 11:30 27阅读 0赞

我们有两个长度相等且不为空的整型数组 A 和 B 。

我们可以交换 A\[i\] 和 B\[i\] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。

在交换过一些元素之后，数组 A 和 B 都应该是严格递增的（数组严格递增的条件仅为A\[0\] < A\[1\] < A\[2\] < … < A\[A.length - 1\]）。

给定数组 A 和 B ，请返回使得两个数组均保持严格递增状态的最小交换次数。假设给定的输入总是有效的。

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

A, B 两个数组的长度总是相等的，且长度的范围为 \[1, 1000\]。  
A\[i\], B\[i\] 均为 \[0, 2000\]区间内的整数。

思路： 现在一看没有思路的题，估计就只有动态规划来做了。  
这里很秀。  
定义状态dp\[2\]\[len\] dp\[0\]\[len\] 代表从0…i当前不替换的数组递增最小交换次数，dp\[1\]\[len\]代表从0…以i替换的最小交换次数。

class Solution {
        
        public int minSwap(int[] A, int[] B) {
        
            int len = A.length;
            int[][] dp = new int[2][len];
            for (int i[]:dp) {
        
                Arrays.fill(i,Integer.MAX_VALUE);
            }
    
            dp[0][0] = 0;
            dp[1][0] = 1;
            for (int j = 1;j < len;j++) {
        
                if (A[j] > A[j-1] && B[j] > B[j-1]) {
        
                    // 不动
                    dp[0][j] = Math.min(dp[0][j],dp[0][j-1]);
        // 一起动  A[1,3].B[1,2]-->A[1,2].B[1,3]两数组都是递增
                    dp[1][j] = Math.min(dp[1][j],dp[1][j-1]+1);
                }
                if (A[j] > B[j-1] && B[j] > A[j-1]) {
        
                    // 前一个交换
                    dp[0][j] = Math.min(dp[0][j],dp[1][j-1]);
                    // 后一个交换
                    dp[1][j] = Math.min(dp[1][j],dp[0][j-1] + 1);
                }
            }
            return Math.min(dp[0][len-1],dp[1][len-1]);
        }
    }