Please explain how you implement the dynamic programming solution.

Shortest path counting: A chess rook can move horizontally or vertically to any square in the same row or the same column of a chessboard. Find the number of shortest paths by which a rook can move from one corner of a chessboard to the diagonally opposite corner. The length of a path is measured by the number of squares it passes through, including the first and the last squares. Solve the problem: a) by a dynamic programming algorithm