Question

5. Let F(n, m) denote the number of paths from top-left cell to bottom-right cell in a (n x m) grid (that only permits moving right or moving down). It satisfies the recurrence relation F(n, m) F(n-1, m) + F(n, m-1) What should be the initial condition for this recurrence relation? (Hint: What would be the number of paths if there was only a single row or a single column in the grid?)[5] Convince yourself that F(n, m) gives correct number of paths for small values of m and n. A brute-force implementation of F(n, m) using the above recurrence relation will be computationally expensive (with several repeated calculations and total number of additions increasing exponentially) Devise a dynamic-programming approach to compute F(n, m) by storing previous values in a table. Write the pseudo code for it and show the output for a 4 x 5 grid. [10]

Answer 1

(1)To count all the possible paths from top left cell to bottom right cell in a mXn grid with the constraints that from each cell you can either move only to right or down.

Recurrentce relation
initial condition
if m==1 or n==1 then numberOfPaths(m,n) = 1
else numberOfPaths(m,n) = numberOfPaths(m-1, n) + numberOfPaths(m, n-1);

(2)//C++ program

#include <iostream>
using namespace std;

int numberOfPaths(int m, int n)
{
  
int F[m][n];
  
for (int i = 0; i < m; i++)
F[i][0] = 1;
  
for (int j = 0; j < n; j++)
F[0][j] = 1;
  
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
  
F[i][j] = F[i-1][j] + F[i][j-1];
  
}
return F[m-1][n-1];
}
  
int main()
{ int m=4 , n=5;

cout << "number of paths in a Grid of "<<m<<"x"<<n<<" is "<<numberOfPaths(m, n);
return 0;
}

//sample output

CAUsers IshuManish\Documents numberOfPaths.exe umber of paths in a Grid of 4x5 is 35 3624 seconds with rocess exited after .3 return value Press any key to continue - -