最短コース問題（４）を紹介します。
問題（４）
道路が碁盤の目になっているn×nの町がある。点線のところは通れないとして、左上隅の交差点aから右下隅の交差点bまでの最短コースの数は何通りあるか考察せよ。
ただし、道路は、縦にn+1本、横にn+1本あるとし、交差点間の距離は同じとする。
また、交差点を(i,j)で表す。すなわち、下方向にi+1本目、右方向にj+1本目の道路が交わる交差点である。
左上隅の交差点は(0,0)、
左下隅の交差点は(n,0)、
右上隅の交差点は(0,n)、
右下隅の交差点は(n,n)
とする。
左上隅交差点(0,0)から交差点(i,j) (i≦j)までの最短コースの数をf(i,j)とする。
f(i,j)が満たす漸化式を求めよ。
最短コース問題（３）の解答例を示します。
問題（３）の解
最短コースは42通りある。
最短コース問題（３）を紹介します。
問題（３）
道路が碁盤の目になっている5×5の町がある。点線のところは通れないとして、左上隅の交差点aから右下隅の交差点bまでの最短コースの数は何通りあるか考察せよ。
ただし、道路は、縦に6本、横に6本あるとし、交差点間の距離は同じとする。
最短コース問題（２）の解答例を示します。
問題（２）の解
列挙すると、14通りある。
交差点間を右への移動をR、下への移動をDとすると、
[1] RDRDRDRD
[2] RDRDRRDD
[3] RDRRDDRD
[4] RDRRDRDD
[5] RDRRRDDD
[6] RRDDRDRD
[7] RRDDRRDD
[8] RRDRDDRD
[9] RRDRDRDD
[10] RRDRRDDD
[11] RRRDDDRD
[12] RRRDDRDD
[13] RRRDRDDD
[14] RRRRDDDD
つぎのように、各交差点に最短コースの数を記入していくことで、求めることもできる。
最短コース問題（２）を紹介します。
問題（２）
道路が碁盤の目になっている4×4の町がある。点線のところは通れないとして、左上隅の交差点aから右下隅の交差点bまでの最短コースの数は何通りあるか考察せよ。
ただし、道路は、縦に5本、横に5本あるとし、交差点間の距離は同じとする。
最短コース問題（１）の解答例を示します。
問題（１）の解
列挙すると、5通りある。
交差点間を右への移動をR、下への移動をDとすると、
[1] RDRDRD
[2] RDRRDD
[3] RRDDRD
[4] RRDRDD
[5] RRRDDD
最短コース問題（１）を紹介します。
問題（１）
道路が碁盤の目になっている2×2の町がある。点線のところは通れないとして、左上隅の交差点aから右下隅の交差点bまでの最短コースの数は2通りある。
ただし、道路は、縦に3本、横に3本あるとし、交差点間の距離は同じとする。
