题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？

思路
这是一道典型的动态规划题，假设finish位置为[i,j]，设到达[i,j]的路径数为d[i][j]，
则有d[i][j] = d[i][j-1] + d[i-1][[j]，所以可以利用一个二维数组存储到达网格中每个位置的路径数。设起始位置为[0,0]。

1.时间复杂度o(n^2) 空间复杂度为o(n^2)

    int uniquePaths(int m, int n){int i,j;//定义一个二维数组存储到达每个位置的路径vector<vector<int>> d(n,vector<int>(m));//设起始位置为[0,0]for(i = 0; i< n; i++){for( j = 0; j < m; j++)//如果终点位置与起始位置在同一行上或者在同一列上，则必定只有一条路径到达终点if(i == 0 || j == 0)d[i][j] = 1;elsed[i][j] = d[i-1][j] + d[i][j-1];}return d[n-1][m-1];   //二维数组的最后一个元素存储着最终终点的路径数}

2.改进使其空间复杂度为o(n)。

    int uniquePaths(int m, int n){//d刚开始是到达第一行每个格子的路径数vector<int> d(m,1);int i,j;for(i = 1; i< n; i++){//随着行数的变大 对d进行改变 存储的是第i+1行每个格子的路径数//等于它当前本身加上它前一个格子的路径条数for( j = 1; j < m; j++)d[j] += d[j-1];}return d[m-1];}