不同路径
思路：由于不能回退，因此每一格只能来自上一格或左边一格，因此dp数组中每个格子只要将这两个格子的值相加即可。
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m,vector<int>(n));
for(int i=0;i<m;i++)dp[i][0]=1;
for(int j=0;j<n;j++)dp[0][j]=1;
for(int x=1;x<m;x++){
for(int y=1;y<n;y++){
dp[x][y]=dp[x-1][y]+dp[x][y-1];
}
}
return dp[m-1][n-1];
}
};写题的时候想了一下，不能像昨天那样压缩到三个int解决问题，但是发现可以压缩到一个一维数组
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> 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];
}
};
作者：代码随想录
链接：https://leetcode.cn/problems/unique-paths/solutions/2562792/dai-ma-sui-xiang-lu-leetcode62bu-tong-lu-ncye/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。同时还有难以理解的数学优化。到达左下角，共需向右m-1次，向下n-1次，因此要走m+n-2次，只要在这m+n-2次中选择m-1步向下走即可。注意这种想法（算阶乘）极其容易溢出。如下面的错误示范，不能把分子分母分开算。
class Solution {
public:
int uniquePaths(int m, int n) {
int numerator = 1, denominator = 1;
int count = m - 1;
int t = m + n - 2;
while (count--) numerator *= (t--); // 计算分子，此时分子就会溢出
for (int i = 1; i <= m - 1; i++) denominator *= i; // 计算分母
return numerator / denominator;
}
};
作者：代码随想录
链接：https://leetcode.cn/problems/unique-paths/solutions/2562792/dai-ma-sui-xiang-lu-leetcode62bu-tong-lu-ncye/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。正确做法是：
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;
}
};
作者：代码随想录
链接：https://leetcode.cn/problems/unique-paths/solutions/2562792/dai-ma-sui-xiang-lu-leetcode62bu-tong-lu-ncye/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。不同路径 II
题目链接：63. 不同路径 II - 力扣（LeetCode）
思路：对于障碍物，就不初始化，计算dp时也直接跳过就好了。
哪个啥篮子把障碍物堵门啊？？
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m=obstacleGrid.size();
int n=obstacleGrid[0].size();
vector<vector<int>> dp(m,vector<int>(n,0));
if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) //如果在起点或终点出现了障碍，直接返回0
return 0;
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
for(int i=1;i<m;i++){
for(int j=1;j<n;j++)
if(obstacleGrid[i][j]==0)
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
return dp[m-1][n-1];
}
};标签：vector,路径,int,numerator,第三十九,随想录,denominator,obstacleGrid,dp From： https://www.cnblogs.com/Liubox/p/18059051