Count Grid Paths with No Three Equal Moves

Given an integer n, imagine moving on a square grid from the origin at (0, 0) to (n, n). Each step goes either one unit to the right (R) or one unit upward (U), so every path uses exactly n moves of each type. A path is invalid if it ever takes three consecutive moves in the same direction. In other words, the move sequence may not contain RRR or UUU. Return the number of valid paths. Example 1: Explanation: All arrangements of two R moves and two U moves are valid because…