2013-最短経路-解説
- 正解は「18」通り
- 黄色の×は通れません。
- あるつなぎ目に右から至る経路も上から至る経路も戻ることになるので，最短経路ではありません。つまり，ある丸太のつなぎ目に至る最短経路数は，そのつなぎ目に左から至る最短経路数と右から至る最短経路数の和です。
- そこで左下の角のスタート地点（ビ太郎の家(S)）から始めて，下の図のように今いるつなぎ目に至る経路数を右と上のつなぎ目に足していけば，右上の角のゴール（ビーバー公園(G)）に至る最短経路が 18 と分かります。
- 解説
- この解法は，動的計画法と呼ばれる手法の一例です。動的計画法では，部分問題を考え，容易に解ける小さな部分問題を先に解き，その答えを活用して解を求めていきます。
- この場合の部分問題は，あるつなぎ目に至る最短経路数です。
注があるものを除き, このサイトの内容物は
