• 注册
    • 今日签到
    • 连续签到

    暂没有数据

    暂没有数据

    • 查看作者
    • Leetcode: 62. Unique Paths

      62. Unique Paths
      Medium


      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?


      Above is a 7 x 3 grid. How many possible unique paths are there?

      Note: m and n will be at most 100.

      Example 1:

      Input: m = 3, n = 2Output: 3Explanation: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 = 3Output: 28

      class Solution:
          def uniquePaths(self, m: int, n: int) -> int:
              arr = [[1]*m]*n
              for numhigh in range(1,n):
                  for numwide in range(1,m):
                      arr[numhigh][numwide] = arr[numhigh-1][numwide] + arr[numhigh][numwide-1]
              print(arr)         
              return arr[n-1][m-1]

      Here is the process:

      1. set all column to 1, or you can just set the  first column and row to 1
      2. go from the second column and row, which just add the upper and left

      3. do the same method till the end and return the last block value.

      The time complexity is O(mn) because we do mn calculation to it.

      space complexity is O(mn) for creating the mn blocks.


      1 1 1 1 1 1 1
      1
      1

      1 1 1 1 1 1 1
      1 2 3 4 5 6 7
      1

      1 1 1 1 1 1 1
      1 2 3 4 5 6 7
      1 3 6 10 15 21 28

      纽约州·法拉盛
    • 0
    • 1
    • 0
    • 226