LeetCode题目之腾讯精选练习（50题）：不同路径

我会带着你远行 2024-04-18 16:42 95阅读 0赞

# 题目 #

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？  
![在这里插入图片描述][20190909182037917.png]  
例如，上图是一个7 x 3 的网格。有多少可能的路径？

**说明**：m 和 n 的值均不超过 100。

**示例 1**:

输入: m = 3, n = 2
    输出: 3
    解释:
    从左上角开始，总共有 3 条路径可以到达右下角。
    1. 向右 -> 向右 -> 向下
    2. 向右 -> 向下 -> 向右
    3. 向下 -> 向右 -> 向右

**示例 2**:

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

## 算法实现 ##

public int UniquePaths(int m, int n)//动态规划
    {
        
        int[] a = new int[m];
        for (int i = 0; i < m; i++)
        {
        
            a[i] = 1;
        }
        for (int i = 1; i < n; i++)
        {
        
            for (int j = 1; j < m; j++)
            {
        
                a[j] += a[j - 1];
            }
        }
        return a[m - 1];
    }

## 执行结果 ##

**执行结果** : 通过  
**执行用时** : 52 ms, 在所有 C\# 提交中击败了94.05%的用户  
**内存消耗** : 13.6 MB, 在所有 C\# 提交中击败了17.65%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

## 小的总结 ##

刚开始按照自己的想法，设计了递归的算法，但是超时了。于是看了解析，学习了动态规划和排列组合的方法，但是排列组合的方法c\#乘法会溢出。同时还找到了递归做法的优化方法，即用二维数组储存前面已算出路径数。

## 改进前的算法 ##

public int UniquePaths(int m, int n)//递归
    {
        
        if (m == 1 || n == 1)
            return 1;
        if (m == 2)
            return n;
        else if (n == 2)
            return m;
        else
            return UniquePaths(m - 1, n) + UniquePaths(m, n - 1);
    }

执行结果：  
![在这里插入图片描述][20190909184535776.png]

## 改进后的算法 ##

static int[,] a = new int[101, 101];
    public int UniquePaths(int m, int n)//递归
    {
        
        if (m == 1 || n == 1)
            return 1;
        if (m == 2)
            return n;
        else if (n == 2)
            return m;
        if (a[m, n] > 0)
            return a[m, n];
        a[m - 1, n] = UniquePaths(m - 1, n);
        a[m, n - 1] = UniquePaths(m, n - 1);
        a[m, n] = a[m - 1, n] + a[m, n - 1];
        return a[m, n];
    }

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

[20190909182037917.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c8a87fcdb84d47e7accd247fda56f5c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/3cac7369ba34478fadc2c34f93b86316.png
[20190909184535776.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/38eb4a4d1db7445f8a1d4b37e4fbbdab.png
[20190909185340497.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/568b9f15872f4f28aa56a4ab32ccbbc7.png