Math Dynamic Programming Matrix Tabulation
Learner Level

Implement the uniquePathsInGrid method that counts paths from the top-left cell to the bottom-right cell in a grid.

The input contains two integers, rows and cols, representing the size of a grid. Your task is to count how many unique paths exist from the top-left cell to the bottom-right cell.

From each cell, you may move only right or down. For example, in a 3 x 7 grid, there are 28 unique paths.

Example 1
Input:
rows (int) = 3
cols (int) = 7
Return:
(int) 28
Example 2
Input:
rows (int) = 3
cols (int) = 2
Return:
(int) 3
Example 3
Input:
rows (int) = 1
cols (int) = 5
Return:
(int) 1

Use dynamic programming because the number of paths to a cell depends on smaller subproblems.

There is only one way to reach any cell in the first row: keep moving right. There is also only one way to reach any cell in the first column: keep moving down.

For every other cell, the number of paths is the sum of paths from the top cell and the left cell.

Pseudocode:

function uniquePathsInGrid(rows, cols):
    dp = 2D array of size rows x cols filled with 0
    for r from 0 to rows - 1:
        dp[r][0] = 1
    for c from 0 to cols - 1:
        dp[0][c] = 1
    for r from 1 to rows - 1:
        for c from 1 to cols - 1:
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    return dp[rows - 1][cols - 1]
Run your code to see the result.