1、思路

• dp[i][j]表示从坐标(0, 0)走到坐标(i, j)的路径总共有多少条；

• 初始化：二维数组dp的第一行及第一列初始化为0，因为在这些边缘路径上只有一种走法；

• 当前状态只能够通过上方或者左方的两个状态转移而来，故dp[i][j] = dp[i - 1][j] + dp[i][j - 1]；

• 时间复杂度为 $O(nm)$ ，空间复杂度为 $O(nm)$ 。

2、代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(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];
    }
};

3、优化空间效率

• 当前状态只与前两行的状态有关，那么只需要创建一个2行的二维数组（滚动数组）即可；

• 时间复杂度为 $O(nm)$ ，空间复杂度为 $O(n)$ 。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(2, vector<int>(n, 0));

        for (int j = 0; j < n; ++ j) dp[0][j] = 1;

        for (int i = 1; i < m; ++ i)
        {
            dp[i % 2][0] = 1;
            for (int j = 1; j < n; ++ j)
            {
                dp[i % 2][j] = dp[(i + 1) % 2][j] + dp[i % 2][j - 1];
            }
        }

        return dp[(m - 1) % 2][n - 1];
    }
};

4、进一步优化空间效率

• 在计算dp[i][j]时只需要用到dp[i - 1][j]和dp[i][j - 1]，而且使用过一次后这俩元素就不再需要了，只需要创建一个一维数组即可；

• 循环体内的dp[j] += dp[j - 1]可以看成dp[j] = dp[j] + dp[j - 1]，其中等号右边的dp[j]相当于上一条的dp[i - 1][j]，dp[j - 1]相当于上一条的dp[i][j - 1];

• 时间复杂度为 $O(nm)$ ，空间复杂度为 $O(n)$ 。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 1);               //初始化

        for (int i = 1; i < m; ++ i)
        {
            for (int j = 1; j < n; ++ j)
            {
                dp[j] += dp[j - 1];
            }
        }

        return dp[n - 1];
    }
};