[LeetCode] 62. Unique Paths

62. 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.

 

 

My Code

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]

        for i in range(1, n):
            for j in range(1, m):
                dp[j][i] = dp[j-1][i]+dp[j][i-1]

        return dp[m-1][n-1]

 

Approach

- Base cases : 

dp[0][j] = 1

dp[i][0] = 1

- Dynamic Programming:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

 

Why [[0]*7] * 3 Fails

- [0] *  7 creates a list with 7 zeros: [0, 0, 0, 0, 0, 0, 0]

- [[0] * 7] * 3 duplicates the same list reference 3 times, so all rows in the resulting 2D list refer to the same inner list object

dp = [[0] * 7] * 3
print(dp)
# Output: [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]]

 

- Since all rows point to the same list object, modifying one row affects all rows.

dp = [[0] * 7] * 3
print(dp)
# Output: [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]]

 

How to fix it.

To create a proper 2D list where each row is independent, you need to create the inner lists individually.

dp = [ [0] * 7 for _ in range(3) ]

 

- The for _ in range(3) ensures that each row is created independently

- Each iterain of the comprehension creates a new list [0] * 7

- Now, modifying one row does not affect others.

 

Improved

def uniquePaths(m, n):
    dp = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]
    return dp[-1]

 

-Each row is build iteratively, using values from the previous row (sotred in the same array).

- The value of d[j] is updated as :

dp[j] = dp[j] + dp[j-1]