縦と横は独立に移動しているので、東西のみの移動を考慮した際、最後に最も東にいる移動経路の数を求めることを考えます。
また、左折回数と右折回数を管理することで、今西に進んでいるか東に進んでいるかは容易に判断することができます。

よって、

$dp[i][j]$ $:=$ $i$ 回東西方向の移動をした時点で、西から $j$ 番目にいるような移動経路の通り数

とするDPにおいて、累積和を用いて更新することでこのDPは $O(NH)$ で解くことができます。

南北についても同様に考えることができるので、この問題は \(O(N(H+W))\) で解くことができました。なお、メモリの関係上DPテーブルとして配列を 2 つ用意し、交互に更新を行うことで削減することを推奨します。