CodingInterviewQuestions/Leetcode/Leetcode Problem 62 Unique Paths.txt at master · akuchotrani/CodingInterviewQuestions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
62. Unique Paths
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Example 1:

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 -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
Example 2:

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


Hint to solve: use dynamic programming. remember there only going left and down is allowed. Initialize first row and col of grid to 1. Calculate remaining by sum of ways of top and left cell.

class Solution:

    def uniquePaths(self, m: int, n: int) -> int:
        grid = [[0]*m]*n

        #print(grid)

        #Fill the first row with 1. Since there is only one way to reach all cells.
        for i in range(0, n):
            grid[i][0] = 1

        #Fill the first col with 1 since there is only one way to reah all cells.
        for i in range(0, m):
            grid[0][i] = 1

        #All other cells can be reached by top and left cells. Total ways would be sum of left and right
        for i in range(1, n):
            for j in range(1, m):
                grid[i][j] = grid[i-1][j] + grid[i][j-1]

        #print(grid)
        return grid[n-1][m-1]