abduction - 誘拐 (Abduction) Editorial by Mitsubachi
縦と横は独立に移動しているので、東西のみの移動を考慮した際、最後に最も東にいる移動経路の数を求めることを考えます。
また、左折回数と右折回数を管理することで、今西に進んでいるか東に進んでいるかは容易に判断することができます。
よって、
南北についても同様に考えることができるので、この問題は \(O(N(H+W))\) で解くことができました。なお、メモリの関係上DPテーブルとして配列を 2 つ用意し、交互に更新を行うことで削減することを推奨します。
posted:
last update: