Problem: Unique Paths in a Grid

The task is to calculate the total number of unique paths a robot can take to reach the destination from the top-left corner to the bottom-right corner in a grid of size m x n. The robot can only move down or right at any step.

Explanation of Dynamic Programming Approach:

This problem is solved using Dynamic Programming (DP), where we build up the solution step by step using previously computed values.

Steps:

1. Grid Setup:

   • Create a 2D array dp where dp[i][j] represents the number of ways to reach the point (i, j) from (0, 0).

2. Base Cases:

   • The robot can only move right or down. Hence, the number of ways to reach any cell in the last row or the last column is 1 (since there is only one way to move to those cells — either always right or always down).
   • Set dp[m-1][n-1] = 1, and initialize the last row and the last column with 1 because there’s only one path to the destination from any of those cells.

3. DP Transition:

   • For each cell, calculate the number of ways to reach it by adding the number of ways to reach the cell below it (dp[i+1][j]) and the cell to the right of it (dp[i][j+1]).

4. Final Answer:

   • The value at dp[0][0] will be the total number of unique paths from the top-left corner to the bottom-right corner.

Code:

#include <stdio.h>

int PathsNumber(int m, int n)
{
    int dp[m][n]; 
    // Variable-length array, not supported in all compilers.
    
    // Initialize the last row and column to 1
    for (int j = 0; j < n; j++) {
        dp[m - 1][j] = 1;
    }
    for (int i = 0; i < m; i++) {
        dp[i][n - 1] = 1;
    }

    // Fill the dp table from bottom-right to top-left
    for (int i = m - 2; i >= 0; i--) {
        for (int j = n - 2; j >= 0; j--) {
            dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
        }
    }

    // The result is stored in dp[0][0]
    return dp[0][0];
}

int main()
{
    int result = PathsNumber(3, 7);

    printf("The number of paths is: %dn", result);

    return 0;
}

Explanation of Code:

1. Function PathsNumber:

   • The dp array is a 2D array where dp[i][j] represents the number of unique paths to get to the cell (i, j).
   • We initialize the last row and column with 1 because there’s only one way to move to these cells (move only right for the last row and only down for the last column).
   • Then, we iterate from the bottom-right to the top-left and fill in each dp[i][j] with the sum of the number of paths from the cell directly below it (dp[i+1][j]) and the cell directly to the right (dp[i][j+1]).

2. Base Case Initialization:

   • Initialize the last row and column to 1 because there’s only one way to reach those cells (move right or move down).

3. Dynamic Programming Transition:

   • For each cell (i, j), the number of ways to get to (i, j) is the sum of the number of ways to get to (i+1, j) (down) and (i, j+1) (right).

4. Main Function:

   • We call PathsNumber(3, 7) to calculate the number of unique paths for a grid of size 3 x 7, and print the result.

Time and Space Complexity:

• Time Complexity: O(m×n)O(m times n), where mm is the number of rows and nn is the number of columns. We are iterating over all the cells in the grid once.
• Space Complexity: O(m×n)O(m times n) due to the 2D dp array storing the results for each cell.

Example Walkthrough:

For a grid of size 3 x 7 (m=3, n=7):

• Initialization: The last row and the last column will be filled with 1 since there is only one path from these cells to the destination.
• Filling the DP table: Start from the second last row and column, and fill in the values by adding the values from the cell below and the cell to the right.

The result will be the value at dp[0][0], which gives the total number of unique paths.

Example:

For m = 3 and n = 7, the grid looks like:

1  7  21  56  126  252  462
1  6  15  35   70   126  210
1  5  10  20   35   56   84

Thus, the number of unique paths from the top-left corner to the bottom-right corner is 84.

Output:

The number of paths is: 28