Unique Paths

Intuition

This is a typical DP (Dynamic Programming) problem. Since the robot could only move to down or to right, the number of ways to get to position x, y could be calculate by number of ways to get to x - 1, y plus number of ways to get to x, y - 1. So we could use DP get the final answer from top-down, left-right order.

Since every node only relies on it's left and up node, we could only use one 1-D array to save the DP status.

Solution


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