Unique Paths(不同路径)
时间: 2023-11-27 10:04:15 浏览: 35
Unique Paths(不同路径)是一个经典的动态规划问题,其问题描述如下:
一个机器人位于一个 m x n 的网格左上角(起点)。
机器人每次只能向下或向右移动一步。机器人试图达到网格的右下角(终点)。
问总共有多少条不同的路径?
解决这个问题的方法是使用动态规划,具体步骤如下:
1. 定义状态:定义状态 $dp[i][j]$ 表示从起点到达网格 $(i,j)$ 的不同路径数。
2. 初始化状态:对于第一行和第一列,因为机器人只能向下或向右移动,所以到达这些网格的路径数都是 $1$。
3. 状态转移:对于网格 $(i,j)$,可以从上方网格 $(i-1,j)$ 或左方网格 $(i,j-1)$ 到达。因此,到达网格 $(i,j)$ 的不同路径数等于到达上方网格和左方网格的路径数之和,即 $dp[i][j] = dp[i-1][j] + dp[i][j-1]$。
4. 最终结果:最终结果即为到达终点网格 $(m,n)$ 的不同路径数,即 $dp[m][n]$。
下面是C++代码实现:
```c++
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 1)); // 初始化为1,因为第一行和第一列的路径数都为1
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1]; // 状态转移
}
}
return dp[m-1][n-1]; // 最终结果
}
```
时间复杂度为 $O(mn)$,空间复杂度为 $O(mn)$。