**一. 题目描述** A robot is located at the top-left corner of a m  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?  Above is a 3 * 7 grid. How many possible unique paths are there? Note: m and n will be at most 100. **二. 题目分析** 题目的大意是机器人在一个矩阵里走路，规定起点、终点和走路的方向，问走完全程总共有几种走法。该题首先想到用深度优先搜索来做，但是结果是超时。可使用动态规划来做，设状态为`k[i][j]`，表示从起点`(0, 0)`到达`(i, j)`的路线条数，则状态转移方程为： ~~~ k[i][j]=k[i-1][j]+k[i][j-1] ~~~ 使用动态规划时，需注意边界条件的设定。 以下代码使用new创建一维数组（数组大小为`m * n`）并将其作为二维数组使用，第`i`行、`j`列的元素可表示为：`k[i * n + j]` ，这样创建二维数组的好处是内存连续，但表示不够直观。 **三. 示例代码** ~~~ #include <iostream> using namespace std; class Solution { public: // 深搜，会超时 int uniquePaths(int m, int n) { if (m <= 0 || n <= 0) return 0; if (m == 1 || n == 1) return 1; return uniquePaths(m - 1, n) + uniquePaths(m, n - 1); } // 动态规划 int uniquePaths2(int m, int n) // 动态规划 { int *k = new int[m * n]; // 到两条边处各点的走法只有一种 for (int i = 0; i < m; ++i) k[i * n] = 1; for (int j = 0; j < n; ++j) k[j] = 1; for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { k[i * n + j] = k[(i - 1) * n + j] + k[i * n + j - 1]; } } int result = k[(m - 1) * n + n - 1]; delete [] k; return result; } }; ~~~  **四. 小结** 事实上，如果只是求出路线的种数，完全可以将该问题转化为数学问题。假设一个`m`行`n`列的矩阵，机器人从左上走到右下总共需要的步数是`m + n - 2`，其中向下走的步数是`m - 1`，因此问题变成了在`m + n - 2`个操作中，选择`m – 1`个时间点向下走，选择方式有多少种，可用以下公式算出：  若考虑向右走的情况，则步数为`n - 1`，问题也可解释为在`m + n - 2`个操作中，选择`n – 1`个时间点向右走的方法有多少种，公式：