This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money

describe

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 = 7
Output: 28
Copy the code

Example 2:

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 -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
Copy the code

Example 3:

Input: m = 7, n = 3
Output: 28
Copy the code

Example 4:

Input: m = 3, n = 3
Output: 6
Copy the code

Note:

1 <= m, n <= 100
It's guaranteed that the answer will be less than or equal to 2 * 109.
Copy the code

parsing

The upper left corner is the starting position, and the lower right corner is the ending position. How many different paths can you take from the starting position to the ending position?

You can use backtracking if m and n are small, but since they are both too large, we use dynamic programming to solve the problem:

  • Initialize a two-dimensional list dp of m x n size with all 1 elements, each representing a different number of paths from the starting position to the current position
  • Iterate over all elements except the first row and column, dp[I][j] = dp[I][j-1] + dp[i-1][j] at each position, representing the number of different paths from the start position to the current position, the number of different paths from the start position to the left position plus the number of different paths from the start position to the top position
  • At the end of the traversal, dp[-1][-1] is the answer, that is, the number of different paths from the start position to the end position

answer

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[1]*n for _ in range(m)]
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i][j-1] + dp[i-1][j]
        return dp[-1][-1]
        	      
		
Copy the code

The results

Given in Python online submissions for Unique Paths. Memory Usage: Submissions in Python online submissions for Unique Paths.Copy the code

parsing

Df [j] = df[j]+ DF [j-1] is equivalent to the above solution dp[I][j] = DP [I][J-1]+ DP [i-1][j], which can save a lot of memory.

answer

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        df = [1] * n
        for i in range(1, m):
            for j in range(1,n):
                df[j] += df[j-1]
        return df[-1]
Copy the code

The results

Given in the Python online submissions. Memory Usage: 10 ms Submissions in Python online submissions for Unique Paths.Copy the code

parsing

In fact, it is the wisest way to find rules by mathematical means and solve problems by direct calculation. However, difficult problems generally cannot find rules.

answer

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        return math.factorial(m+n-2)/(math.factorial(n-1) * math.factorial(m-1))
Copy the code

The results

Given in the Python online submissions. Memory Usage: Submissions in Python online submissions for Unique Paths.Copy the code

Similar to the topic

  • 63. Unique Paths II
  • 980. Unique Paths III

Original link: leetcode.com/problems/un…

Your support is my biggest motivation