Buckets:
Unique Paths MEDIUM
There is an m x n grid where you are allowed to move either down or to the right at any point in time.
Given the two integers m and n, return the number of possible unique paths that can be taken from the top-left corner of the grid (grid[0][0]) to the bottom-right corner (grid[m - 1][n - 1]).
You may assume the output will fit in a 32-bit integer.
Example 1:
![[unique-paths.avif]]
Input: m = 3, n = 6
Output: 21
Example 2:
Input: m = 3, n = 3
Output: 6
Solution
The problem can be solved using bottom up dynamic programming approach. We start from the bottom-left corner, which is the destination. We need to create a DP matrix of size m + 1 * n + 1 which will serve as the path tracing. Then we loop over the dp matrix starting from row m and column n, and fill each cell using the sum of it's existing value, the value of cell below it and right of it. Final answer will be the value of cell 0, 0.
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
ROW, COL = m, n
dp = [[0 for _ in range(COL + 1)] for _ in range(ROW + 1)]
dp[ROW-1][COL-1] = 1
for i in range(ROW - 1, -1, -1):
for j in range(COL -1, -1, -1):
dp[i][j] += dp[i + 1][j] + dp[i][j + 1]
return dp[0][0]
Xet Storage Details
- Size:
- 1.37 kB
- Xet hash:
- b1f0659388511e9b3d5923e29801298b43bef394d6610c839d8c5ac0d0258a36
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.