unique_paths
1from collections import defaultdict 2 3 4# @leet start 5class Solution: 6 def uniquePaths(self, m: int, n: int) -> int: 7 """ 8 This question asks us to find the unique paths to the bottom right square 9 if we can only go down or right. 10 11 The intuition here is that since we can only go down or right, any tile 12 where we are on the first row or first col only has one way to get there 13 (always right or always down). Thus, we can create a DP array, where 14 the first row and first col are always 1, and then for every other square 15 we know that we can get to the square in the sum of the ways of the 16 square above and the square before the current square. 17 18 Finally, we return the count of paths of the square we want, which is 19 `dp[m-1][n-1]`. 20 21 I did this using a defaultdict since it requires less setup than a DP array. 22 """ 23 dp = defaultdict(lambda: 1) 24 25 for i in range(1, m): 26 for j in range(1, n): 27 dp[(i, j)] = dp[(i - 1, j)] + dp[(i, j - 1)] 28 29 return dp[(m - 1, n - 1)] 30 31 32# @leet end 33 34 35def test(): 36 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def uniquePaths(self, m: int, n: int) -> int: 8 """ 9 This question asks us to find the unique paths to the bottom right square 10 if we can only go down or right. 11 12 The intuition here is that since we can only go down or right, any tile 13 where we are on the first row or first col only has one way to get there 14 (always right or always down). Thus, we can create a DP array, where 15 the first row and first col are always 1, and then for every other square 16 we know that we can get to the square in the sum of the ways of the 17 square above and the square before the current square. 18 19 Finally, we return the count of paths of the square we want, which is 20 `dp[m-1][n-1]`. 21 22 I did this using a defaultdict since it requires less setup than a DP array. 23 """ 24 dp = defaultdict(lambda: 1) 25 26 for i in range(1, m): 27 for j in range(1, n): 28 dp[(i, j)] = dp[(i - 1, j)] + dp[(i, j - 1)] 29 30 return dp[(m - 1, n - 1)]
def
uniquePaths(self, m: int, n: int) -> int:
7 def uniquePaths(self, m: int, n: int) -> int: 8 """ 9 This question asks us to find the unique paths to the bottom right square 10 if we can only go down or right. 11 12 The intuition here is that since we can only go down or right, any tile 13 where we are on the first row or first col only has one way to get there 14 (always right or always down). Thus, we can create a DP array, where 15 the first row and first col are always 1, and then for every other square 16 we know that we can get to the square in the sum of the ways of the 17 square above and the square before the current square. 18 19 Finally, we return the count of paths of the square we want, which is 20 `dp[m-1][n-1]`. 21 22 I did this using a defaultdict since it requires less setup than a DP array. 23 """ 24 dp = defaultdict(lambda: 1) 25 26 for i in range(1, m): 27 for j in range(1, n): 28 dp[(i, j)] = dp[(i - 1, j)] + dp[(i, j - 1)] 29 30 return dp[(m - 1, n - 1)]
This question asks us to find the unique paths to the bottom right square if we can only go down or right.
The intuition here is that since we can only go down or right, any tile where we are on the first row or first col only has one way to get there (always right or always down). Thus, we can create a DP array, where the first row and first col are always 1, and then for every other square we know that we can get to the square in the sum of the ways of the square above and the square before the current square.
Finally, we return the count of paths of the square we want, which is
dp[m-1][n-1].
I did this using a defaultdict since it requires less setup than a DP array.
def
test():