不同路径——动态规划

题目一：不同路径

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

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

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

解法一：动态规划

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

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>>dp(m,vector<int>(n,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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

这个解法的空间复杂度为$o(mn)$，利用滚动思想对空间复杂度进行优化：

优化一

当更新每一行的路径数时，只与上一行和本行有关，因此可以定义两个大小为n的数组保存更新信息。

class Solution {
public:
    int uniquePaths(int m, int n) {
        int ans=0;
        vector<int>pre(n,1);
        vector<int>cur(n,1);
        for(int i=1;i<m;++i)
        {
            for(int j=1;j<n;++j)
            {
                cur[j]=pre[j]+cur[j-1];
            }
            pre=cur;
        }
        return pre.back();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

优化二

在优化一中我们使用了pre数组来记录上一行的信息，我们也可以不使用pre数组而只使用cur数组，具体原因：
当我们更新cur[i]的时候(cur
[i]还未完成更新)，cur[i]保存的是到达上一行i位置的路径数(相当于pre[i])。
代码如下：

class Solution {
public:
    int uniquePaths(int m, int n) {
        int ans=0;
        vector<int>cur(n,1);
        for(int i=1;i<m;++i)
        {
            for(int j=1;j<n;++j)
            {
                cur[j]+=cur[j-1];
            }
        }
        return cur.back();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

解法二：数学

从起点到终点共需要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<m;++x,++y)
        {
            ans=ans*x/y;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11

题目二：不同路径II

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

解题思路与题目一类似，只不过需要注意路径中的障碍物，代码如下：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size(),n=obstacleGrid[0].size();
        vector<int>cur(n,1);
        for(int i=0;i<n;++i)
            if(obstacleGrid[0][i])
            {
                for(i;i<n;++i)cur[i]=0;
                break;
            }
        int pre=cur[0];
        for(int i=1;i<m;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(obstacleGrid[i][j])
                    cur[j]=0;
                else if(j==0)
                {
                    cur[j]=pre;
                }    
                else
                    cur[j]+=cur[j-1];
                if(j==0)
                    pre=cur[j];
            }
        }
            
        
        return cur.back();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

在我自己的解法中使用了一个pre变量来记录上一行第一个元素的路径数，然后对官方代码进行学习：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size(), m = obstacleGrid.at(0).size();
        vector <int> 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();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25