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?
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;
}
};
~~~
**四. 小结**
事实上，如果只是求出路线的种数，完全可以将该问题转化为数学问题。假设一个`m`行`n`列的矩阵，机器人从左上走到右下总共需要的步数是`m + n - 2`，其中向下走的步数是`m - 1`，因此问题变成了在`m + n - 2`个操作中，选择`m – 1`个时间点向下走，选择方式有多少种，可用以下公式算出：
若考虑向右走的情况，则步数为`n - 1`，问题也可解释为在`m + n - 2`个操作中，选择`n – 1`个时间点向右走的方法有多少种，公式：
';