Unique Paths - Dynamic Programming - Leetcode 62

0:00 - Read the problem
0:55- Drawing solution
8:20 - Coding Solution

leetcode 62

#dynamic #programming #python

[sviatoslavnovosiadlyi]

Been working as SWE for 8 years. Never had to deal with problems like that but I do understand its necessary for interview. Was having really hard time understanding concept on coming with solution on my own but your videos are pure gold..

[tuminspace]

The intro itself is so addictive that when I try to solve a problem
I'd say it out
"Hello everyone let's solve somemore neetcode today"

[HR-pzts]

Your way of teaching is so good that I didn't even had to wait for you to code and I coded it myself just by using your logic. Thanks man!

[haosmark]

Great explanation. Code can be simplified. There's no reason to hold 'newRow', you can just do it all with 'row', and there's no reason to track backwards, you can move forward (which feels more intuitive) with return row[-1] at the end.

[tsuu]

Here is my solution using math:

Let's say the width is 7 and the height is 3, which means your path will consists of 6R and 2D in any order. So in 8 possible moves, we fill 6 moves with R, which is 8C6 (or 8C2 if you consider D instead) ways total.

The generalized formula would be (w+h-2)C(w-1)

[quirkyquester]

Great explanation! Thx teacher!
def uniquePaths(self, m: int, n: int) -> int:
dp = [1] * n
# do it m - 1 times, (rows need to calculate)
# cos bottom row is [1] * n already
for r in range(m - 1):
newDp = dp[:] # this doesn't matter, as long as length is same and last item is 1 meaning it's the edge it will work
for c in range(n - 2, -1, -1):
newDp[c] = newDp[c + 1] + dp[c]
dp = newDp
return dp[0]

[nyferox]

Great explanation. The answer for the constant time solution is just (m + n - 2) choose (m - 1), which is equal to (m + n - 2)! / ((m - 1)! * (n - 1)!). This is because you know that you have to have (m - 1) moves down and (n - 1) moves right, so you just need to choose where those (m - 1) downs or (n - 1) rights go and then you are done.

[manuelese]

Man this is tough for me. This problem is above me. Greetings from Argentina. I really like your content

[sentinel-yl]

* You don't need to start from the last position and move backwards. You can start from the first position and move to the target (which seems more natural).
* There is no need to create new arrays for each new row (that is inefficient). You can reuse the same array throughout all the rows.

Java:
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[j] += dp[j-1];
return dp[n-1];

[director]

I understand these solutions, but I could never think of these. How exactly do I go about learning the method to derive, is it just a ton of practice?, great video by the way

[dhij]

I was surprised you didn't take your usual approach using dfs and dp set. This is another implementation with the same concept for anyone who might be interested.

def uniquePaths(self, m: int, n: int) -> int:
dp = {}

def dfs(r, c):
if r == m - 1 and c == n - 1:
return 1
if (r, c) in dp:
return dp[(r, c)]
if (r < 0 or r == m or
c < 0 or c == n):
return 0

dp[(r, c)] = dfs(r+1, c) + dfs(r, c+1)

return dp[(r, c)]

return dfs(0, 0)

[rams]

Thanks man.. I like your voice and the way you go through the problem.. clear explanation...

[akialter]

I had to do this problem in ASM in a course. Professor asked that we needed to use the minimum amount of static/dynamic instructions. Without dp the code was extremely big footprints-wise. Showed a use case of DP given the constraint.

[---elpq]

Came here to say the way I solved this was by realizing that the filled out spaces matched the values of Pascal's Triangle, just rotated. So if you move m spaces down the right side of the triangle and n spaces down the left side, the intersection of those two diagonals is going to be the solution.

For example for m = 7 and n = 3, go 7 spaces down the right side of the triangle to reach the level (1, 6, 15, 20, 15, 6, 1) and 3 spaces down the left to reach level (1, 2, 1), the intersection is at level 9 (1, 8, 28, 56, 70, 56, 28, 8, 1), and 3 spaces in. There is already an equation for finding a value of Pascal's Triangle at level A and position B, which is A! / B!(A - B)!

Note that m and n DO NOT EQUAL A and B, because they represent a grid that corresponds to the values of the triangle rotated 90 degrees. To get the A and B values you have to compute:

B = min(m, n) - 1 //We subtract 1 because the math formula defines the top of the triangle as the 0th level. This is the position on the level that we need to get to.
A = m + n - 2//We subtract 1 each for m and n, and then add them together to get the level that our solution will be on.

My final solution in Java:

import java.math.BigInteger;
class Solution {
public int uniquePaths(int m, int n) {
int b = Math.min(m, n) - 1;
int a = m + n - 2;
return - b))).intValue();
}


public BigInteger fact(int val) {
BigInteger factorial = BigInteger.ONE;
for (int i = 1; i <= val; i++) {
factorial =
}
return factorial;
}
}

[RandomShowerThoughts]

this was a fantastic video and perfectly describes how to tackle this type of problem

[yingjielian]

Your explanation is the best among all of the explanations on the internet!

[pekarna]

Alternative approach:
We need to take 6 steps right and 2 down, in various order.
That means, a permutation of 2 sets of A == 6 and B == 2.
That means: (A + B) ! / (A! x B!)

E.g. 8! / (2! x 6!) = 28.

This is only possible because of the homogenity of the underlying graph (grid).
The problem of high numbers can be addressed by cancelling out the common parts of the factorials.
Then it can be sped up by memoization.
Even without that, this is faster than 82 %:

class Solution {
fun uniquePaths(m: Int, n: Int): Int {
val a = m -1
val b = n-1
return ( fact(a + b) / fact(a) / fact(b) ).toInt()
}
}


fun fact(num: Int): BigInteger {
var factorial = 1.toBigInteger()
for (i in num downTo 2) {
factorial =
}
return factorial
}

[ejaz]

This problem is much easier to solve if you don't use dynamic programming at all.
Its just a permutation problem. Here's a C++ example below that is essentially doing the permutation factorial calculation, but simplifying it first.

class Solution {
public:
int uniquePaths(int m, int n) {
if (m > n) {
std::swap(m, n);
}
long result = 1;
for (int i = 1; i <= m - 1; ++i) {
result = result * (n - 1 + i) / i;
}
return result;
}
};

[vgsuresh]

this is one of the amazing explanation for the problem.

[draugno]

This was a piece of cake after the prev. dp problems from this playlist (solved in 5 mins) :D