I also want to know the recurrence

Short Answer

dp[k][h] := the answer if (K, H) = (k, h); W is fixed
dp[k][h] can be calculated by dp[k-1][h-1], dp[k][h-1] and dp[k+1][h-1]

Full Answer

dp is written as A in editorial.
We want to calculate dp[K][H].

I'll call horizontal line that lies on a-th and b-th vertical line (a, b).

First, dp[1][0] = 1, dp[2][0] = dp[3][0] = ... = dp[W][0] = 0 because there's no horizontal line.

Second, think when calculating h = i. Note that we already know dp[any][i - 1].
For each k = a, there's 3 choices; go straight, go right, or go left.

go straight

We can make neither (a, a + 1) nor (a - 1, a).

dp[a][i] += dp[a][i-1] * (no. of ways to make pairs that doesn't affect the above pairs; editorial call it Y)

NOTE : Y is no. of ways to make pairs whose y-coordinate = i. The others (whose coordinate < i) are counted by dp[a][i - 1].

go left

We should make (a - 1, a), and can make neither (a - 2, a - 1) nor a(a, a + 1).

dp[a-1][i] += dp[a][i-1] * (no. of ways to make pairs that doesn't affect the above pairs; editorial call it X)

go right

same as left. Define Z similarly.

Okay, now we want to calculate X, Y and Z for each k.

X, Y and Z can be calculated by brute force (O(2^W)).

You can get AC now.

Editorial introduce the way to speed up using Fibonacci sequence.

Speeding up that my solution uses is like it.

Main idea of DP is same.

https://beta.atcoder.jp/contests/abc113/submissions/3715464

I wrote some comments in English to clarify.