Leetcode: Unique Paths

Love The Way You Lie 2022-08-07 12:45 35阅读 0赞

题目：

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?

![robot_maze.png][]

Above is a 3 x 7 grid. How many possible unique paths are there?

**Note:** *m* and *n* will be at most 100.

思路分析：

又是动态规划问题。

开一个f\[m\]\[n\]的数组，数组元素初始化为1，递推公式f\[i\]\[j\] = f\[i-1\]\[j\] + f\[i\]\[j-1\]，空间时间复杂度O(m\*n)。

（可以将f\[m\]\[n\]理解成为从f\[0\]\[0\]到达f\[m\]\[n\]的路径个数。那很自然的就会f\[i\]\[j\] = f\[i-1\]\[j\] + f\[i\]\[j-1\]。有感觉递推公式还不是能很好想出来的，继续加强训练吧！）

C++参考代码：

class Solution
    {
    public:
        int uniquePaths(int m, int n)
        {
            //将vector中的元素初始化为1
            vector<vector<int>> v(m, vector<int>(n, 1));
            for (int i = 1; i < m; ++i)
            {
                for (int j = 1; j < n; ++j)
                {
                    v[i][j] = v[i - 1][j] + v[i][j - 1];
                }
            }
            return v[m - 1][n - 1];
        }
    };

代码还可以进一步优化，利用滚动数组。

开一个f\[n\]的数组，数组元素初始化为1，递推公式f\[j\]=f\[j\]+f\[j-1\]，空间时间复杂度O(n)。等号左边的f\[j\]相当于f\[i\]\[j\] = f\[i-1\]\[j\] + f\[i\]\[j-1\]的f\[i\]\[j\]，等号右边的f\[j\]相当于f\[i-1\]\[j\]，而f\[j-1\]相当于f\[i\]\[j-1\]。

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

下面再来探讨一下这道题的数学本质：机器人从左上角走到右下角，总共走m+n-2步，其中m-1步往下走，n-1步往右走，本质上就是一个组合问题，也就是从m+n-2个不同元素中每次取出m-1或者n-1个元素的组合数。Cn+m-2m-1=Cn+m-2n-1所以我们可以选择m-1和n-1中小的进行计算！

根据组合公式：Cnm=Anm/Amm=n(n-1)...(n-m+1)/m!

class Solution
    {
    public:
        int uniquePaths(int m, int n)
        {
            long long numerator = 1;
            long long denominator = 1;
            int small = m < n ? m - 1: n - 1;
            int big = m < n ? n- 1 : m - 1;
            for (int i = 1; i <= small; ++i)
            {
                numerator *= (big + small - i + 1);
                denominator *= i;
            }
            return int(numerator / denominator);
        }
    };

而组合公式Cmn=Cmn-1\+Cm-1n和f\[i\]\[j\] = f\[i-1\]\[j\] + f\[i\]\[j-1\]的f\[i\]\[j\]是何其的相似。

而组合公式有对应和杨辉三角：

C01C11                    1  1

C02C12C22             1  2  1

C03C13C23C33       1 3  3  1

[robot_maze.png]: http://leetcode.com/wp-content/uploads/2014/12/robot_maze.png