[ LeetCode  ]

LeetCode 62: Unique Paths

本题主要考察动态规划(DP)算法,同时也可用数学方法解决。

题目

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

解法一:数学(排列组合问题)

因为表格有 m 行 n 列,所以机器人总共要走 $m-1$ 次“下”,$n-1$ 次“右”,故问题转化为下面这样的排列组合问题:

下下右下下右下……

容易知道,这样的组合数总共有:

这样直接用公式来算,空间复杂度为 $O(1)$,时间复杂度为 $O(m+n)$(计算阶乘)。具体实现就不写了。

解法二:DP (mxn 数组)

机器人在每个一点,要么向下走,要么向右走。假设目标点坐标为 $(0,0)$,起始点坐标为$(m-1,n-1)$,用 $dp[i][j]$ 来表示从 $(i,j)$ 出发到达终点的路径总数,那么可以得到一个递推公式:

从终点一直往前递推到起始点,就可以算出起始点到终点的路径总数。C++实现如下:

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];
    }
};

此算法的空间复杂度和时间复杂度都是 $O(mn)$。

解法三:DP(两行数组)

由于每次计算都仅仅使用到上一行,之前的行都没用,所以可以仅仅用两行数组完成更新:

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> pre(n, 1), cur(n, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                cur[j] = pre[j] + cur[j - 1];
            }
            swap(pre, cur);
        }
        return pre[n - 1];
    }
};

此时空间复杂度变成了 $O(n)$。

解法三:DP(一行数组)

注意到刚才的程序中有交换 precur,所以现在的 pre 其实就是之前的 cur,我们完全不需要这个 pre,直接在 cur 上增量更新即可,实现如下:

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

此时空间复杂度同样是 $O(n)$,但实际上大约是上一个程序空间占用的一半。