不同路径——动态规划

题目一：不同路径

解法一：动态规划

优化一优化二 解法二：数学 题目二：不同路径II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

本题目使用动态规划来解决比较简单，定义dp[i][j]数组为到达(i，j)点的路径数。由题中所述机器人只能向下向右走，可得递推公式为
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][j]=dp[i-1][j]+dp[i][j-1] dp[i][j]=dp[i−1][j]+dp[i][j−1]
确定边界条件：
dp数组的第一行和第一列路径为1。
代码如下：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector>dp(m,vector(n,1));
        for(int i=1;i 
这个解法的空间复杂度为
    
     
      
       
        o
       
       
        (
       
       
        m
       
       
        n
       
       
        )
       
      
      
       o(mn)
      
     
    o(mn)，利用滚动思想对空间复杂度进行优化：
 
优化一 
当更新每一行的路径数时，只与上一行和本行有关，因此可以定义两个大小为n的数组保存更新信息。
 
class Solution {
public:
    int uniquePaths(int m, int n) {
        int ans=0;
        vectorpre(n,1);
        vectorcur(n,1);
        for(int i=1;i 
优化二 
在优化一中我们使用了pre数组来记录上一行的信息，我们也可以不使用pre数组而只使用cur数组，具体原因：
 当我们更新cur[i]的时候(cur
 [i]还未完成更新)，cur[i]保存的是到达上一行i位置的路径数(相当于pre[i])。
 代码如下：
 
class Solution {
public:
    int uniquePaths(int m, int n) {
        int ans=0;
        vectorcur(n,1);
        for(int i=1;i 
解法二：数学 
从起点到终点共需要m+n-2步,其中向下需要m-1步，向右需要n-1步，因此从起点到终点的路径数等于m+n-2步中选择m-1步向下移动的方案数。
 C(m+n-2,m-1)=(m+n-2)!/[(m-1)!(n-1)!]=[n(n+1)…(n+m-2)!]/(m-1)!]
 代码如下：
 
class Solution {
public:
    int uniquePaths(int m, int n) {
        long long ans=1;
        for(int x=n,y=1;y 
题目二：不同路径II 
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
 
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
 
网格中的障碍物和空位置分别用 1 和 0 来表示。
 
解题思路与题目一类似，只不过需要注意路径中的障碍物，代码如下：
 
class Solution {
public:
    int uniquePathsWithObstacles(vector>& obstacleGrid) {
        int m=obstacleGrid.size(),n=obstacleGrid[0].size();
        vectorcur(n,1);
        for(int i=0;i 
在我自己的解法中使用了一个pre变量来记录上一行第一个元素的路径数，然后对官方代码进行学习：
 
class Solution {
public:
    int uniquePathsWithObstacles(vector>& obstacleGrid) {
        int n = obstacleGrid.size(), m = obstacleGrid.at(0).size();
        vector  f(m);

        f[0] = (obstacleGrid[0][0] == 0);//对起点元素进行初始化
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
    				//与自己方法的不同之处：遇到障碍物时就把f[i]置为0，
    				//又因为元素的改变会影响到之后的每一行，
    				//因此与设置pre变量跟踪每行第一个元素的状态效果相同。
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    f[j] += f[j - 1];
                }
            }
        }

        return f.back();
    }
};