Unique Paths

最后更新于:2022-04-01 22:56:53

**一. 题目描述** 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? ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5f0086f5.jpg) 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 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; } }; ~~~ ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5f019645.jpg) **四. 小结** 事实上,如果只是求出路线的种数,完全可以将该问题转化为数学问题。假设一个`m`行`n`列的矩阵,机器人从左上走到右下总共需要的步数是`m + n - 2`,其中向下走的步数是`m - 1`,因此问题变成了在`m + n - 2`个操作中,选择`m – 1`个时间点向下走,选择方式有多少种,可用以下公式算出: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5f026b59.jpg) 若考虑向右走的情况,则步数为`n - 1`,问题也可解释为在`m + n - 2`个操作中,选择`n – 1`个时间点向右走的方法有多少种,公式: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5f036b77.jpg)
';