题目描述
https://leetcode-cn.com/problems/unique-paths/
思路
我看到这个题一下子想到的思路是组合数，这不就是初中数学的填空题嘛，实际相当于机器人总共走了 m + n - 2步，其中 m - 1 步向右走，n - 1 步向下走。那么从 m + n - 2步里挑m-1步有几种挑法，c(m+n-2,m-1)啊。但是直接这样实现，有一个样例没过，我也不知道为啥，可能是大数溢出问题，不想追究了。
下面说说dp思路。
image.png
原来这跟之前那道 Climbing Stairs 很类似，那道题是说可以每次能爬一格或两格，问到达顶部的所有不同爬法的个数。而这道题是每次可以向下走或者向右走，求到达最右下角的所有不同走法的个数。那么跟爬梯子问题一样，需要用动态规划 Dynamic Programming 来解，可以维护一个二维数组 dp，其中 dp[i][j] 表示到当前位置不同的走法的个数，然后可以得到状态转移方程为: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，这里为了节省空间，使用一维数组 dp，一行一行的刷新也可以。
代码
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> dp(m, 1);
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[j] = dp[j] + dp[j-1];
}
}
return dp[m-1];
}
};
网友评论