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

链接：801.使序列递增的最小交换次数
难度：Hard
标签：数组、动态规划
简介：返回 使 nums1 和 nums2 严格递增 所需操作的最小次数 。

题解 1 - cpp

• 编辑时间：2022-10-10
• 执行用时：236ms
• 内存消耗：117.2MB
• 编程语言：cpp
• 解法介绍：dp[i][0|1]表示 i 为结尾下标时，交换和不交换的最小交换次数。

class Solution {
public:
    int minSwap(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<vector<int>> dp(n, vector<int>(2, n));
        dp[0][0] = 0;
        dp[0][1] = 1;
        for (int i = 1; i < n; i++) {
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                dp[i][0] = min(dp[i][0], dp[i - 1][0]);
                dp[i][1] = min(dp[i][1], dp[i - 1][1] + 1);
            }
            if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
                dp[i][0] = min(dp[i][0], dp[i - 1][1]);
                dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1);
            }
        }
        return min(dp[n - 1][0], dp[n - 1][1]);
    }
};