There are m+n-2 steps to make and choosing the positions of (m-1) steps down (or n-1 steps right) uniquely determines the path, so the answer is always (m+n-2) choose (m-1)
The number of paths basically form a rotated Pascals triangle so theres an analytic solution once you transform the grid coordinates into the appropriate inputs for the binomial coefficients equation.
@maxencegitton377: The only correct answer👍 Any path from start to finish is a combination of (m-1) D's and (n-1) R's where D means a move down and R means a move right, e.g. DRDR. So, the answer is 6, not 9. Apart from that, this is a math problem rather than a coding problem.
Um, I don't think @maxencegitto377 will see your comment since it's disjointed and could be lost in the other replies. You could use the reply function so the system sends him a notification of your reply.
@@AsianCurls My replies to _most_ posts are regarded as a new post by YT when using my mobile phone, I _did_ reply to maxencegitton377. On my pc any post or reply is rejected. Anyone?
@GregHogg - From which condition of your code would it enter to mark ret[1][0] = 1 How did you write ret[1][0] as 1 in as shown in the video ? if it enters the else: part ret[1][0] = ret[1][-1] (left element)+ ret[0][0] (top element) so to calculate ret[1][0] code is referring to ret[1][-1] which is not yet available! This same thing happens for every ret[i][0] , basically every element in the 1st column for each row.
It works because we have set the whole 2D array ret to zeroes at start, but i would think this case of out of bound should be avoided or addressed in a cleaner way.
an important consideration to talk through is whether you can achieve each of the time complexities and WHY OR WHY NOT! you started with an O( N * M ) solution, can we find a solution that is linear in the side lengths or a closed form O(1)? no matter what the optimal solution you need to understand and articulate why further improvements are not possible. If you know it mentioning a proof is great.
@roelsfotoos i mean after each move, he can choose 1 or 2 steps to move forward. It's not likely moving with 1 step completely and moving with two steps completely.
When i ran the test cases, I found the dynamic programming (tabulation) based approach faster than this factorial based formula. So, yes, programming approach matters even over matchmatical simple formula!
@@howhello354 Another problem with the factorial solution is that it goes to really big numbers above 2^31 quickly and that can create bugs. Thank you.
There are many clever ways you could solve this problem. You can use a 2D array to use dynamic programming. But the most optimal way is to make your way not from the start but from the end. I forgot the solution but I remember solving it.
Let A indicate going down, and B indicate going to the right. m rows means m-1 A's needed. n cols means n-1 B's needed. Now we need the total number of distinct arrangements of such A's and B's. That is (m+n-2)!/((m-1)!*(n-1)!).
The answer fails by matter of the constraints - namely the question notes the answer will be less then or equal to 2E9 , and is quite slow. a = max(m,n) b = min(m,n) answer = a * (a+1)/2 * .... * (a+b-2)/(b-1) this can be implemented with 13 bytes memory - int64 (8 bytes) for intermediate result - int32 (4 bytes) for a - byte (1 byte) for b (as max=17, ref below) - byte (1 byte) for a counter up to b timing: at most 15 multiplications and 15 divisions
```python def robot_path(w=3, h=3): m = [] for r in range(h): row = [] for c in range(w): if r == 0 or c == 0: row.append(1) else: row.append(row[-1] + m[r-1][c]) m.append(row) return m width, height = map(int, input().split()) path = robot_path(width, height) for row in path: print(*row) ```
this is 2d dynamic programming ,and your solution is simply wrong , you must solve it bottom-up , you find that how many ways there is to reach the destination and you find the first row will always be one and you solve it the other way. both climbing stair (1d dynamic ) and this is totally wrong
I don't know why after all these times , you didn't learn that the solutions to dynamic programing is always from bottom-up , you always case the smallest amount to solve your way from front , you did that both on climbing stairs and this problem , no this is not the way you solve it , you better see the neet-code channel 2d dynamic programming solutions and you will understand that your way is simply wrong
