問題
$ N $ 個の足場があり、左から $ i $ 番目の足場(足場 $ i $ とする)の高さは $ h_i $ です。
ウサギは以下の2種類の行動を繰り返すことで、足場1から足場 $ N $ に移動します。
🔹足場 $ i - 2 $ から足場 $ i $ に、コスト $ | h_{i-2} - h_i | $ かけて移動する。
🔹足場 $ i - 1 $ から足場 $ i $ に、コスト $ | h_{i-1} - h_i | $ かけて移動する。
足場 $ 1 $ から足場 $ N $ に移動するのに、最短コストのルートを1つ出力して下さい。
解き方・ソースコード
前々回の記事では同じ問題の最短コストを求めましたが、今回は最短コストで移動する際のルート(経路)を求める問題となります。
この問題ではゴールから順番にスタートへの経路を考えることで解くことができます。
まずは、前々回記事と同様に動的計画法を使って最短コストを求めます。
この時に作成した $ dp $ を確認すると次のように最適解(最短コストとなるルート)を復元することができます。
🔹$ dp[x] = dp[x - 1] + | H[x - 1] - H[x] | $ の場合:方法Aを選ぶ
🔹$ dp[x] = dp[x - 2] + | H[x - 2] - H[x] | $ の場合:方法Bを選ぶ
なお、上の2つの条件両方を満たす場合は、方法A・方法Bどちらを選んでも構いません。
[Google Colaboratory]
1 | #--------- 入力例 ---------- |
[実行結果]
[5] [5, 4] [5, 4, 2] [5, 4, 2, 0] 解: 1 → 3 → 5 → 6
最短コストにするためには1 → 3 → 5 → 6というルート(経路)であることが確認できました😊