最短コース問題(4)を紹介します。
問題(4)
道路が碁盤の目になっている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)が満たす漸化式を求めよ。