A robot can move horizontally or vertically to any square in the same row or in the same column of a board. Find the number of the shortest paths by which a robot can move from one corner of a board to the diagonally opposite corner. The length of a path is measured by the number of squares it passes through, including the rst and the least squares. Write the recurrence relation if you solve the problem by a dynamic programming algorithm.

A-) R(i,j) = { min(R(i-k,j) +k , R(i,j-k) +k) for all 1<= k <=n}

B-) R(i,j) = min(R(i-1,j) +1 , R(i,j-1) +1)

C-) R(i,j) = max(R(i-1,j) +1 , R(i,j-1) +1)

D-) R(i,j) = R(i-1,j) + R(i, j-1) for all I,j<=8

E-) R(i+k,j+k) = { min(R(i,j) +k , R(i,j) +k) for all 1<= k <=n}