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) =
3cols (int) =
7Returns (int)
28Example 2
Input
rows (int) =
3cols (int) =
2Returns (int)
3Example 3
Input
rows (int) =
1cols (int) =
5Returns (int)
1Use 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]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run