2010JOI予選5 通勤経路 解説

問題リンク

解説

初歩的な動的計画法の問題です。

を、 行目かつ 列目のマスにいる状態とし、残り2つの添字で「どちらの方向から来たか、次に曲がれるか」を保持します。

この動的計画法を と の昇順で回すことで解けます。

このように、典型的な動的計画法に単純な条件が加わっただけの場合は、その条件を示す添字を付け加えることで簡単に解けることがあります。 条件がいくつかある場合、ひとつずつ別々に考えるのも手です。