Hi, I need help with this problem. Specifically, I need help understanding the \texttt{DP} transitions in the editorial. I don’t understand how this can only be solved in O(n) memory (the editorial isn’t clear on this). I got the observations on the two possible sequences that could work, and got to the \texttt{DP}, but idk how to reduce the DP to linear time and memory.

It’s pretty clear that the editorial code takes O(n) time and memory.

I don’t really understand the editorial transitions.

```
dp1[x + 1] = add(dp1[x + 1], dp1[x + 1]);
dp1[x + 1] = add(dp1[x + 1], dp1[x]);
if (x > 0) dp2[x - 1] = add(dp2[x - 1], dp2[x - 1]);
if (x > 0) dp2[x - 1] = add(dp2[x - 1], dp1[x - 1]);
dp2[x + 1] = add(dp2[x + 1], dp2[x + 1]);
```

I don’t really understand any of these transitions. Could you explain these to me?