Minimum Swaps To Make Sequences Increasing

题目
We have two integer sequences A and B of the same non-zero length.

We are allowed to swap elements A[i] and B[i]. Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, A and B are both strictly increasing. (A sequence is strictly increasing if and only if A[0] < A[1] < A[2] < ... < A[A.length - 1].)

Given A and B, return the minimum number of swaps to make both sequences strictly increasing. It is guaranteed that the given input always makes it possible.

分析
Example:
A 1 10 200 300
B 1 100 20 30
Apparently, if we swap the 3rd and 4th position, we make 2 swaps.
If we swap the 2ed position, we only have to make 1 swap.
Therefore, it requires us to try out all possible paths and make decisions about whether or not to swap at each position i.
Sounds like a recursion problem that can be solved with dynamic programming.
One thing to note: whether or not the i-1th position was swapped could affect the number of min swaps needed for the sequence starting at ith position. Be sure to take this into account when designing your dp data structure.

答案

class Solution {
    public int minSwap(int[] A, int[] B) {
        // dp[i]: what's the minimum number of swaps to make sequence A[i...n] and B[i...n] increasing?
        //Map<long[], Long> dp = new HashMap<>();
        long[][] dp = new long[A.length][2];
        for(long[] row : dp) Arrays.fill(row, -1);
        return (int)recur(A, B, 0, 0, dp);
    }

    public void swap(int[] A, int[] B, int i) {
        int t = A[i];
        A[i] = B[i];
        B[i] = t;
    }

    public long recur(int[] A, int[] B, int curr_pos, int swapped, long[][] dp) {
        if(curr_pos >= A.length) return 0;
        if(dp[curr_pos][swapped] != -1) return dp[curr_pos][swapped];

        long swap_no, swap_yes;
        if(curr_pos > 0 && (A[curr_pos-1] >= A[curr_pos] || B[curr_pos-1] >= B[curr_pos]))
            swap_no = Integer.MAX_VALUE;
        else
            swap_no = recur(A, B, curr_pos + 1, 0, dp);


        swap(A, B, curr_pos);
        if(curr_pos > 0 && (A[curr_pos-1] >= A[curr_pos] || B[curr_pos-1] >= B[curr_pos]))
            swap_yes = Integer.MAX_VALUE;
        else
            swap_yes = recur(A, B, curr_pos + 1, 1, dp);
        swap(A, B, curr_pos);
        // swap_yes = recur(A, B, curr_pos + 1, 1, dp);


        long ans = Math.min(swap_yes + 1, swap_no);
        dp[curr_pos][swapped] = ans;
        return ans;
    }
}