Minimum number of swaps to make two arrays strictly increasing I'm trying to understand the solution of the following problem (LC 801):

Given two arrays, A and B, of the same nonzero length, find the minimum number of swaps (A[i] &lt;--&gt; B[i]) to make A and B strictly increasing.
The solution is guaranteed to exist for the given input data.
Example:
Input: A = [1, 2, 9, 4, 5, 6], B = [7, 8, 3, 10, 12, 13]
Output: 1 (swap 9 and 3)

The solutions posted by others consider a dp array, of size [2, A.size()], which is filled as follows:
int N = static_cast&lt;int&gt;(A.size());
std::vector&lt;std::vector&lt;int&gt;&gt; dp(2, std::vector&lt;int&gt;(N, N));

for (int ii = 1; ii &lt; N; ++ii) {
  if (A[ii - 1] &gt; A[ii] &amp;&amp; B[ii - 1] &gt; B[ii]) {
    dp[0][ii] = std::min(dp[0][ii], dp[0][ii - 1]);
    dp[1][ii] = std::min(dp[1][ii], dp[1][ii - 1] + 1);
  }
  if (A[ii] &gt; B[ii - 1] &amp;&amp; B[ii] &gt; A[ii - 1]) {
    dp[0][ii] = std::min(dp[0][ii], dp[1][ii - 1]);
    dp[1][ii] = std::min(dp[1][ii], dp[0][ii - 1] + 1);
  }
}

return std::min(dp[0][N - 1], dp[1][N - 1]);

How to think / develop the idea for the solution?
It is clear that in the case the monotony is broken, i.e. A[ii] &lt;= A[ii - 1] we need to swap, but, from trying a few test cases, this is not the optimal way to do the swaps.
$dp[b][i]$ denotes the minimum number of swaps needed to make the first $i$ elements of both arrays strictly increasing where $b$ is a boolean flag denoting whether we've swapped $A[i]$ and $B[i]$ (or $\infty$ if this minimum doesn't exist).
The key observation is that we only care about what $A[i-1]$ and $B[i-1]$ are when calculating $dp[0/1][i]$. This means that we can calculate $dp[0/1][i]$ using only $A[i-1]$, $B[i-1]$, $A[i]$, $B[i]$ and $dp[0/1][i-1]$ in $\mathcal O(1)$ time. (The recurrences are shown in the code you posted).
The answer is clearly $\min(dp[0/1][N])$, and this solution runs in $\mathcal O(N)$ time.