Approach #1: Dynamic Programming [Accepted]
The cost of making both sequences increasing up to the first
i columns can be expressed in terms of the cost of making both sequences increasing up to the first
i-1 columns. This is because the only thing that matters to the
ith column is whether the previous column was swapped or not. This makes dynamic programming an ideal choice.
natural1), the cost of making the first
i-1 columns increasing and not swapping the
i-1th column; and
swapped1), the cost of making the first
i-1 columns increasing and swapping the
Now we want candidates
s2), the costs of making the first
i columns increasing if we do not swap (or swap, respectively) the
For convenience, say
a1 = A[i-1], b1 = B[i-1] and
a2 = A[i], b2 = B[i].
a1 < a2 and
b1 < b2, then it is allowed to have both of these columns natural (unswapped), or both of these columns swapped. This possibility leads to
n2 = min(n2, n1) and
s2 = min(s2, s1 + 1).
Another, (not exclusive) possibility is that
a1 < b2 and
b1 < a2. This means that it is allowed to have exactly one of these columns swapped. This possibility leads to
n2 = min(n2, s1) or
s2 = min(s2, n1 + 1).
Note that it is important to use two if statements separately, because both of the above possibilities might be possible.
At the end, the optimal solution must leave the last column either natural or swapped, so we take the minimum number of swaps between the two possibilities.
Time Complexity: .
Space Complexity: .
Analysis written by: @awice.