I'm not able to memoize this question in leetcode ? What am i doing wrong?

Question

Question link: https://leetcode.com/problems/unique-paths/

Code with memoization but takes the same amount of time :https://leetcode.com/submissions/detail/672801459/

Code without memoization: https://leetcode.com/submissions/detail/672800593/

Code with memoization but takes the same amount of time :https://leetcode.com/submissions/detail/672801459/

I've written code for memoization but something doesn't work please tell me what am i doing wrong.

Answer 1

Memoization is not the problem

I just think that even if the implementation works the way you intend it, it is still too slow, you could have up to one billion path to explore wich could each take more than 100 steps.

Try it with combinatorics

Another approach is to look at the problem from a combinatorics side: notice how each path could be represented by a list of down or right moves so the total number of paths is just the number of ways to arrange the down and up moves

From the original question, we can see that there are m-1 moves down and n-1moves up. In combinatorics, we say that the result is the combination of m-1 in (m-1) + (n-1)

Here is some code that would do that:

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        def factorial(a):
            out = 1
            for i in range(1, a+1):
                out *= i
            return out

        def combination(a, b):
            out = 1
            for i in range(b-a+1, b+1):
                out *= i
            return out // factorial(a)

        return combination(m-1, (m-1)+(n-1))