LeetCode 0062 - Unique Paths
# Hints
DP
组合数学
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
A robot is located at the top-left corner of a 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 grid. How many possible unique paths are there?
Example 1:
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:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
Example 2:
Input: m = 7, n = 3
Output: 28
Constraints:
It's guaranteed that the answer will be less than or equal to .
# 题意
有一个 的网格,初始站在 处,每一步只能向右或向下移动,求走到 处有多少种不同的移动方案。
# 题解
方法1:
考虑动态规划,设 表示走到 的方案数。
状态转移方程:
$\begin{cases} dp[i][1] = 1, &(1 \le i \le m)\ dp[1][j] = 1, &(1 \le j \le n)\ dp[i][j] = dp[i-1][j] + dp[i][j-1], &(2 \le i \le m,\ 2 \le j \le n)\ \end{cases}$
则 即为答案。时间复杂度为 。
方法2:
考虑从 走到 共有 步,其中 步为向下、 步为向右,那么问题转化为从 步中选择 步作为向下移动,显然答案为 。
用公式或递推求解组合数均可。然而对于本题的数据范围,直接公式求解会发生过程量溢出,需要妥善调整计算过程,较为复杂,而递推求解则要方便得多。递推求解的时间复杂度为 ,但是远远跑不满。
# AC代码(DP)
class Solution {
public:
int uniquePaths(int m, int n) {
// 初始化
int dp[m + 1][n + 1];
// 递推
for (int i = 1; i <= m; i ++) {
dp[i][1] = 1;
}
for (int j = 1; j <= n; j ++) {
dp[1][j] = 1;
}
for (int i = 2; i <= m; i ++) for (int j = 2; j <= n; j ++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
// 返回
return dp[m][n];
}
};
# AC代码(组合数学)
class Solution {
public:
int uniquePaths(int m, int n) {
// 特判
if (m == 1 || n == 1) {
return 1;
}
if (m > n) {
return uniquePaths(n, m);
}
// 初始化
int C[m + n][m];
// 递推
C[0][0] = 0;
for (int i = 1; i <= m + n - 2; i ++) {
C[i][0] = 1;
}
for (int i = 1; i <= m - 1; i ++) {
C[i][i] = 1;
}
for (int i = 2; i <= m + n - 2; i ++) for (int j = 1; j <= min(i - 1, m - 1); j ++) {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
// 返回
return C[m + n - 2][m - 1];
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01