Unique Paths

Unique Paths

Question:

Given an m * n grid, there is a robot at the top-right corner that wants to go the the bottom-left corner.

The robot can only move right and down. What is the number of possible unique paths that the robot can take to reach the bottom-left corner?

My Line of Thought:

Looking at this problem, this reminded me of some questions back in high school. When I was learning about Combination, there was a similar question to this. I thought that I could simply use that knowledge to solve this question.

Given an m * n grid, the robot must make (m -1) moves to the right and (n-1) moves downward. Robot makes (m + n -2) moves and the unique paths choose which the order in which they move to the right or down. Therefore, the simple answer to this question would be C(m + n - 2, n - 1)

However, pondering about this problem more deeply, I knew there could be more ‘algorithmic’ ‘CS’ way to solve this question.

Breaking down this grid question by making m and n equal to a really small number (1, 2), and expanding how it relates to a bigger value (2,3)… Dynamic Programming to the rescue!

For point in this grid, the unique paths up to that point will simply be the sum of unique paths to the point one above and to the point one left. I could use that knowledge to memoize the values and use DP for solving this problem. I would have to initialize the values to 1, and I could do that for all the points in the first row or column since all the points really only have 1 unique path. For the other points in the grid, it will automatically update even if I set it to 1, so I just initialized the values to 1.

My Implementation:

import math

class Solution(object):
    def uniquePaths(self, m, n):
        math.factorial(m+n-2) / (math.factorial(m - 1) * math.factorial(n - 1)

Or

class Solution(object):
    def uniquePaths(self, m, n):
        dp = [[1] * n] * m
        
        for r in range(1, m):
            for c in range(1, n):
                dp[r][c] = dp[r-1][c] + dp[r][c-1]
        
        return dp[m-1][n-1]

Reflection:

I think I got lucky with this question using the simple math formula, because the DP solution did not come to my mind easily.

Oddily enough, the solution using the basic math was faster in terms of time efficiency even though it was using another module.

I would have to look into how to optimize the memoization for my DP solution, if there is any way to do so