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.