精选50题之 62. 不同路径

青旅半醒 2024-04-18 23:30 43阅读 0赞

### 腾讯精选练习（50 题）之 62. 不同路径 ###

*   *  原题目链接
     *  题目分析
     *  解题分析
     *  代码实现
     *  其他方式
     *  写在最后

## [原题目链接][Link 1] ##

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。  
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。  
问总共有多少条不同的路径？  
![无描述][20190914092216631.png]  
例如，上图是一个7 x 3 的网格。有多少可能的路径？  
说明：m 和 n 的值均不超过 100。

示例 1:

> 输入: m = 3, n = 2  
> 输出: 3

解释:  
从左上角开始，总共有 3 条路径可以到达右下角。

1.  向右 -> 向右 -> 向下
2.  向右 -> 向下 -> 向右
3.  向下 -> 向右 -> 向右

示例 2:

> 输入: m = 7, n = 3  
> 输出: 28

## 题目分析 ##

这是一道可以被认为是关于组合数的数学题。

## 解题分析 ##

横向移动 m - 1 步，纵向移动 n - 1步，共移动（m + n - 2）步。  
这正是组合数C(N, k)的形式。

*  N = m + n - 2
 *  k = min(m - 1, n - 1)（对k进行判断是为了减小计算量）

经公式推导，又可以写成 (n∗(n−1)∗(n−2)∗…(n−k+1))/k!  
(ps. 然而问题就出现在这里)

## 代码实现 ##

快速实现如下

class Solution {
        
    public:
        int uniquePaths(int m, int n) {
        
            if(m < n)
            {
        
            	int temp = m;
            	m = n;
            	n = temp;
            	}
        	int N = m + n - 2;
        	int k = n - 1;
        	int res = 1;
        	while(k >= 1)
            	res = res * (N-- / k--); // 从大乘到小
            return (int) res; 
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]  
运行报错 20算成16。反复检查公式，发现没有问题。无解，开IDE单步调试，然后恍然大悟…  
**int 表示 7/3 = 2，直接向下取整，表示错误。**  
**在整型上表示分数是很不明智的。**

那么用double型呢？也不可以。**double在分数计算以及最后 (int) 转换成整型时有误差和向下取整。** e.g. 56 算成55

那么现在有两种思路，一种是引入斐波那契数列分别求分子分母，再求商；另一种，改变公式。

改变公式的一种迷之方法，不是从大乘到小，而是从小乘到大，居然不会报错?  
其背后的数学原理还没有搞清楚，很迷?

class Solution {
        
    public:
        int uniquePaths(int m, int n) {
        
            if(m < n)
            {
        
                int temp = m;
                m = n;
                n = temp;
            }
            int N = m + n - 2;
            int k = n - 1;
            long res = 1; 
            for (int i = 1; i <= k; i++)
                res = res * (N - k + i) / i; // 从小乘到大。。。
            return (int) res; 
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]  
复杂度分析：

*  时间复杂度：O(N)
 *  空间复杂度：O(1)

Ps.C++ 标准库没有斐波那契、组合数的函数么…

## 其他方式 ##

虽然有一些因为数据结构选择不当引发的问题，但在完成后发现数学方法并没有秒杀这道题，运行时间仍然很长。简单分析，原因是乘法的运算速度？

这道题也有它的“计算机解法”，那就是动态规划。在二维数组中填表求值

定义一个二维数组a\[m\]\[n\]，表示走到这个格子的路径数。由题意容易知道，最上面一行和最左边ll一行可以置为1.  
而每一个格子可以由上面的格子往下走一格或左边的格子往右走一格走到。

class Solution {
        
    public:
        int uniquePaths(int m, int n) {
        
            int dp[m][n]={
        0};
            for(int i=0;i<m;i++)
                dp[i][0]=1;
            for(int j=1;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];
        }
    };

![在这里插入图片描述][20190915125953703.png]

## 写在最后 ##

数据结构、数据结构、数据结构…

[Link 1]: https://leetcode-cn.com/problems/unique-paths/
[20190914092216631.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/950c1b75939f446b859d7dcd2eb74744.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c71cb97e799a40fdb871df1cff9dde43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/6785d46d46f148498918cfb7064b5b23.png
[20190915125953703.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/b9d6be5594f8478ea0ba1dd3187dbf97.png