Wednesday, December 30, 2015

[Leetcode] Unique Path

Problem

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?

Analysis

  • 对于每一格,有两种到达它的方式,即从左边,或者从上边
    • 所以 count[i][j] = count[i-1][j] + count[i][j-1]
  • Time: O(n^2)
  • Space: O(n^2)
    • Space可以进行优化为O(n), 因为计算count每一行的值的时候只需要上一行的信息

Code


No comments:

Post a Comment