题目描述
A robot is located at the top-left corner of a m x 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?
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
- Right -> Right -> Down
- Right -> Down -> Right
- Down -> Right -> Right
解题思路
- DFS思路，复杂度较高，总是超时。
- 考虑找出状态转移方程，使用动态规划来做
- 用dp[i][j]表示i，j这个位置总共有多少种走法。
- 注意到其中四字格，右下角其实是可以用 右上角，左下角 的和推导出来的。
- 即状态转移方程可写为 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
- 在填dp表格之前，要记得先初始化dp[0][i],dp[i][0]
C++代码
class Solution {
public:
int uniquePaths(int m, int n) {
//return fun_helper(m, n, 0, 0);
int dp[n][m] = {0};
for(int i = 0; i < m; i++){
dp[0][i] = 1;
}
for(int i = 0; i < n; i++){
dp[i][0] = 1;
}
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[n - 1][m - 1];
}
/*int fun_helper(int col, int row, int c, int r){
if(col - 1 == c && row - 1 == r){
return 1;
}
if(r < row - 1 && c < col - 1){
return fun_helper(col, row, c + 1, r) + // to right
fun_helper(col, row, c, r + 1); // to down
}
if(r < row - 1){ //
return fun_helper(col, row, c, r + 1); // to down
}
if(c < col - 1){
return fun_helper(col, row, c + 1, r); // to right
}
return 0;
}*/
};
解题思路
- 第一眼还是DFS
- 但注意会报超时错误
- 这时候就要另外想办法
- 其实这个动态规划思想也挺好想的，但要初始化的时候注意
- 第0行，第0列都要初始化为1 // 这里为什么要初始化为1？想一想 从开头横着走，竖着走 最短的话 就是1条，即到达第0行或者第0列位置最少就是1
- 然后dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
- 最后结果为 dp[n - 1][m - 1]
C++代码
class Solution {
public:
int uniquePaths(int m, int n) {
int res = 0;
fun_helper(0, 0, n, m, res);
return res;
/*int dp[n][m] = {0};
for(int i = 0; i < n; i++){
dp[i][0] = 1;
}
for(int i = 0; i < m; i++){
dp[0][i] = 1;
}
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[n - 1][m - 1];*/
}
void fun_helper(int r, int c, int n, int m, int& res){
if(r == n - 1 && c == m - 1){
res++;
return;
}
if(r < 0 || r >= n || c < 0 || c >= m){
return;
}
fun_helper(r + 1, c, n, m, res);
fun_helper(r, c + 1, n, m, res);
}
};
