代码来自随想录和官方题解
class Solution {
public:
int uniquePaths(int m, int n) {
vector> dp(m, vector(n, 0));
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 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];
}
};
// 滚动数组
class Solution {
public:
int uniquePaths(int m, int n) {
vector dp(n);
for (int i = 0; i < n; i++) dp[i] = 1;
for (int j = 1; j < m; j++) {
for (int i = 1; i < n; i++) {
dp[i] += dp[i - 1];
}
}
return dp[n - 1];
}
};
// 也可组合数学解，计算注意避免溢出
class Solution {
public:
int uniquePaths(int m, int n) {
long long numerator = 1; // 分子
int denominator = m - 1; // 分母
int count = m - 1;
int t = m + n - 2;
while (count--) {
numerator *= (t--);
while (denominator != 0 && numerator % denominator == 0) {
numerator /= denominator;
denominator--;
}
}
return numerator;
}
};
// 官方这个解法写得更清楚
class Solution {
public:
int uniquePaths(int m, int n) {
long long ans = 1;
for (int x = n, y = 1; y < m; ++x, ++y) {
ans = ans * x / y;
}
return ans;
}
};
DP O(mn)，组合数 O(m)，但是感觉硬件处理乘法比加法复杂，这个时间复杂度真的能说明组合数解法更快吗？
滚动数组DP 执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户 内存消耗：6 MB, 在所有 C++ 提交中击败了74.03% 的用户 数论 执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户 内存消耗：5.9 MB, 在所有 C++ 提交中击败了78.58% 的用户
力扣测试看不出差别= =保留疑问
