Leetcode: Unique Paths

Leetcode: Unique Paths

题目：

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?

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> v(m, vector(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 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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。