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