Unique Paths - Leetcode 62 - Dynamic Programming (Python)

Please check my playlists for free DSA problem solutions:

My Favorite Courses:

Data Structures & Algorithms:

Python:

Web Dev / Full Stack:

Cloud Development:

Game Development:

SQL & Data Science:

Machine Learning & AI:

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[debajyotisg]

You are my favourite LeetCode explainer channel by a country mile. Your explanations are so clear!

[DJSaez-llor]

I don't often comment on videos, but this was an excellent, excellent solution. I struggled a lot with this problem and DP in general, but you explained it in such a clear way! Thank you so much

[racecarjonny]

Your videos on DP problems are the best on YouTube. Thanks!

[epicman]

There's actually a formula for this:
((m-1)+(n-1))!

(m-1)! * (n-1)!
This is because the problem can also be thought of as how many unique ways you can order the right and down movements.
In the 3x7 example, there are going to be 6 rightwards movements and 2 downwards movements creating an off by one error.
The rest of the formula is unique arrangements of characters with duplicates.

[anjaliputtha]

Great explanation, Thank you Greg.
For some reason, I always like to take the last indices as base case rather than the first one

def uniquePaths(self, m: int, n: int) -> int:
dp = [[1] * n for i in range(m)]
for i in range(m-2, -1, -1):
for j in range(n-2, -1, -1):
dp[i][j] = dp[i+1][j] + dp[i][j+1]
return dp[0][0]

[LoganDrdaCS]

If the first row consists of 1s and the first column consists of 1s, then you can simplify:
```
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = []
for _ in range(m):
dp.append([1] * n)

for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]

return dp[m-1][n-1]
```
This excludes the calculation of the first row & columns, which are already initialized to 1.

Big fan of your channel, by the way! Thanks for what you do.

[tauicsicsics]

Fantastic explanations Greg, best channel ever. Pls try to do all Neetcode 169 and Blind 169. thank you

[anirudd]

in paths function we could just do ' if i == 0 or j == 0 : return 1 ', instead of doing ' if i == j == 0 : return 1 '

[chandlerkenworthy]

I would argue using the same approach as in your video this code is a bit neater and easier to read

dp = [0] * n * m
for mi in range(0, m): # Number of rows
for ni in range(0, n): # Number of columns
i = (mi * n) + ni
if mi == 0 or ni == 0:
dp[i] = 1 # Sides of the grid are always 1s
continue
dp[i] = dp[i-1] + dp[i-n]
return dp[-1]

[broccoli]

Very easy to follow and thanks for covering both approaches. Personally, I prefer the top-down approach.

[Berkerdnmz]

I'm confused about the complexity of the recursive solution. Shouldn't it be 2^(m+n)?

[lng-]

The dp array looks very similar to a rotated Pascal triangle. Interesting.

[sohummisra]

Why not do this?

def unique_paths(rows, cols):

DP = [1] * cols

for i in range(1, rows):
for j in range(1, cols):
DP[j] += DP[j-1]

return DP[cols-1]

[ahmedfakhry]

Your videos are blessings. Keep going please :)