[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