不同路径
可以图论中的深度优先搜索，可以将每一次的选择抽象为二叉树的两个子节点，这样所有的路径集合就被抽象成了一棵二叉树，求的路径数目就是二叉树叶子节点的数目。树的层数为 m+n-1，深搜近似遍历了树的所有节点，因此程序的时间复杂度近似于指数级，是会超时的。
动态规划实现如下，其实还可以用滚动数组的方式进一步做空间优化，当前的状态只与左侧和上面的状态有关，可以只用一个一维数组表示，其自身就是上次遍历（上一行）的值，只需要加上左侧的值就可以得到这次遍历（本行）的值。
class Solution{
public:
int uniquePaths(int m, int n){
// dp[i][j]为到达(i+1,j+1)位置的路径数目
vector<vector<int>> dp(m, vector<int>(n, 0));
for(int i = 0; i < m; i++) dp[0][i] = 1; // 注意模拟m=n=1的情况
for(int i = 0; i < n; i++) dp[i][0] = 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];
}
};
数论的方法：从起点走到终点一共有 m+n-2 步，其中一定有 m - 1 步向下走，所以这道题也可以被建模为组合题。相当于从 m+n-2 个数中挑出 m-1 个不同的数，一共有多少种组合。
但是组合数的计算代码实现需要注意 int 相乘可能会溢出。所以要在计算分子的时候，同时除以分母，不要把分子分母分别算好，然后才除。
class Solution{
public:
int uniquePaths(int m, int n) {
long long result = 1;
int count = m - 1;
int fenmu = m - 1; // 分母从大的一端开始，才更能保证分子不溢出
int t = m + n - 2;
while(count--){
result *= (t--);
while(fenmu != 0 && result % fenmu == 0) {
result /= fenmu;
fenmu--;
}
}
return result;
}
};
不同路径||
注意几点：遇到障碍保持初始状态就好；在对边缘进行初始化时，遇到障碍后面都走不了，要置为0；对起点和终点有障碍物这种特殊情况的模拟。
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));
// 初始化时一旦遇到障碍就结束循环
for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for(int i = 0; i < n && obstacleGrid[0][i] == 0; i++) dp[0][i] = 1;
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(obstacleGrid[i][j] == 1) continue;
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};
同样这道题也能用一维数组优化空间。这种写法要注意判断每一行的第一个元素是否有障碍物，因为状态更新的第二层 for 循环从 j=0 开始，在写 dp[j-1] 要避免溢出。
