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每一行的值的时候只需要上一行的信息