Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

 

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

 

Constraints:

  • 1 <= m, n <= 100
SOLUTION:
class Solution:
    def uniquePathsRec(self, m, n, i, j):
        if i == m - 1 or j == n - 1:
            return 1
        if (i, j) in self.cache:
            return self.cache[(i , j)]
        res = self.uniquePathsRec(m, n, i + 1, j) + self.uniquePathsRec(m, n, i, j + 1)
        self.cache[(i, j)] = res
        return res
    
    def uniquePaths(self, m: int, n: int, i = 0, j = 0) -> int:
        self.cache = {}
        return self.uniquePathsRec(m, n, 0, 0)

Comments

Post a Comment

Popular posts from this blog

Minimum Number of Operations to Move All Balls to Each Box

You have n boxes. You are given a binary string boxes of length n , where boxes[i] is '0' if the i th box is empty , and '1' if it contains one ball. In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1 . Note that after doing so, there may be more than one ball in some boxes. Return an array answer of size n , where answer[i] is the minimum number of operations needed to move all the balls to the i th box. Each answer[i] is calculated considering the initial state of the boxes.   Example 1: Input: boxes = "110" Output: [1,1,3] Explanation: The answer for each box is as follows: 1) First box: you will have to move one ball from the second box to the first box in one operation. 2) Second box: you will have to move one ball from the first box to the second box in one operation. 3) Third box: you will have to move one ball from the first box to the third box in two...
Read more

Efficient Generation of Nth Row of Binomial Coefficient Modulo M

Efficient Generation of Nth Row of Binomial Coefficient Modulo M Efficient Generation of Nth Row of Binomial Coefficient Modulo M Introduction Calculating the binomial coefficient (also known as the combinatorial coefficient) is a common task in mathematics and programming. However, when the modulo M is not prime, finding an efficient method becomes more challenging. In this article, we will explore a technique that allows us to efficiently generate the Nth row of the binomial coefficient modulo M, even when M is not necessarily prime. This technique utilizes prime factorization and a sieve algorithm to achieve efficient computation. The Implementation Let's take a look at the implementation of the technique: from collections import Counter N = 1 + 10 ** 6 v = [False] * N spf = [1] * N for i in range(2, N, 2): spf[i] = 2 for i in range(3, N, 2): if not v[i]: spf[i] = i j = i while j * i 1: ctr[spf[a]...
Read more

Lazy Deletion in Heap: A Wrapper for Python heapq

Lazy Deletion in Heap: A Wrapper for Python heapq Lazy Deletion in Heap: A Wrapper for Python heapq In many programming scenarios, we often encounter situations where we need to maintain a heap data structure and perform operations such as insertion, deletion, and retrieval of the minimum element efficiently. Python provides a built-in module called heapq that offers heap operations. However, the standard heapq module does not provide direct support for lazy deletion, which can be useful in certain cases. In this article, we will explore a wrapper class, Heap , that extends the functionality of the Python heapq library to support lazy deletion in a heap. The Heap Class The Heap class is a wrapper that encapsulates the heapq module to enable lazy deletion in a heap. Let's go through its main methods and their functionalities: __init__(self) : Initializes the Heap instance by creating an empty heap and a defaultdict to track the deleted elements ...
Read more