SHARE
SPREAD
HELP

The Tradition of Sharing

Help your friends and juniors by posting answers to the questions that you know. Also post questions that are not available.

To start with, Sr2Jr’s first step is to reduce the expenses related to education. To achieve this goal Sr2Jr organized the textbook’s question and answers. Sr2Jr is community based and need your support to fill the question and answers. The question and answers posted will be available free of cost to all.

The pleasure of all reading is doubled when one lives with another who shares the same. -Katherine Mansfield

 

#
Authors:
Anany Levitin
Chapter:
Dynamic Programming
Exercise:
8.1 Exercise
Question:7 | ISBN:9780132316811 | Edition: 3

Question

Shortest-path counting A chess rook can move horizontally or vertically to any square in the same row or in 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.
b. by using elementary combinatorics.

TextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbook

Answer

a.

 

Dynamic Programming Algorithm:

To solve this problem using dynamic programming, we can define a 2D array dp[i][j], where dp[i][j] represents the number of shortest paths to reach square (i, j) on the chessboard.

The dimensions of the array will be (n+1) x (n+1), where n is the size of the chessboard.

The base cases for the dynamic programming algorithm will be:

  • dp[1][1] = 1, as there is only one square on the chessboard.
  • dp[i][1] = 1, for 1 <= i <= n, as the rook can only move vertically to reach any square in the first column.
  • dp[1][j] = 1, for 1 <= j <= n, as the rook can only move horizontally to reach any square in the first row.

For other cells (i, j) in the dp array, the number of shortest paths to reach that cell can be calculated using the following recurrence relation:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

The final result will be stored in dp[n][n], which represents the diagonally opposite corner of the chessboard.

Here's the dynamic programming algorithm to find the number of shortest paths:

  1. Initialize the dp array of size (n+1) x (n+1) with all elements set to 0.
  2. Set dp[1][1] = 1.
  3. Set dp[i][1] = 1 and dp[1][j] = 1 for 1 <= i, j <= n.
  4. For i from 2 to n:
    • For j from 2 to n:
      • Set dp[i][j] = dp[i-1][j] + dp[i][j-1].
  5. The result is stored in dp[n][n].

 

b.

Elementary Combinatorics:

Alternatively, we can solve this problem using elementary combinatorics. Since the rook can only move horizontally or vertically, it needs to make a total of (n-1) horizontal moves and (n-1) vertical moves to reach the diagonally opposite corner.

The number of ways to arrange these (n-1) horizontal moves and (n-1) vertical moves can be calculated using the binomial coefficient:

Number of shortest paths = (n-1 + n-1) choose (n-1) = 2(n-1) choose (n-1)

Using the formula for binomial coefficient, the number of shortest paths can be calculated as:

Number of shortest paths = (2n-2)! / ((n-1)! * (n-1)!)

Both the dynamic programming algorithm and the combinatorics approach will yield the same result, giving the number of shortest paths by which a rook can move from one corner of a chessboard to the diagonally opposite corner.

0 0

Discussions

Post the discussion to improve the above solution.