Leetcode算法Java全解答--62. 不同路径

以你之姓@ 2022-04-08 12:14 178阅读 0赞

# Leetcode算法Java全解答–62. 不同路径 #

### 文章目录 ###

*  Leetcode算法Java全解答--62. 不同路径
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

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

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

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

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

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

## 想法 ##

和第70题走楼梯类似，不过这个是二维的，那个是直线的

任何一格位置数据都是通过 他左边一格的数据+上边的数据来的。

比如(7,3)坐标的数据，是通过(6,3) + (7,2)获取到的结果

那么同理可得(6,3)又是根据(5,3)+(6,2)来的，

同理可得(7,2)又是根据(7,1)+(6,2)来的，

这样就能往前推到(1,1)了，这里就是边界条件

这里注意一下，(6,3)和(7,2)都用到了(6,2)的结果，如果每次都去计算(6,2)的值，很浪费时间，

所以我们用一个hashMap保存数据，key就是(6,2)，value就是(6,2)的值

## 结果 ##

超过5.74%的测试案例

时间复杂度/空间复杂度： n/n

## 总结 ##

## 代码 ##

### 我的答案 ###

HashMap hashMap = new HashMap<String, Integer>();
    
      public int uniquePaths(int m, int n) {
        return recuResult(m, n);
      }
    
      public int recuResult(int m, int n) {
        int result = 0;
        if (m == 0 || n == 0) {
          return 0;
        }
    
        if (m == 1 && n == 1) {
          return 1;
        }
    
        if (hashMap.get(m + "+" + n) != null) {
          return (Integer) hashMap.get(m + "+" + n);
        }
    
        result = recuResult(m - 1, n) + recuResult(m, n - 1);
        hashMap.put(m + "+" + n, result);
        return result;
      }

### 大佬们的答案 ###

/**************************************
       * 比我好的答案 better
       * 这个直接用数组求解，速度比我快
       * ***********************************/
      public int better(int m, int n) {
        if (m <= 0 || n <= 0) {
          return 0;
        }
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 1; i < n; i++) {
          dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
          dp[i][0] = 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];
      }

### 测试用例 ###

@Test
    public void test062() {
        // 创建测试案例
        int m1 = 3;
        int n1 = 2;
        int m2 = 7;
        int n2 = 3;
    
        // 测试案例期望值
        int expResult1 = 3;
        int expResult2 = 28;
    
        // 执行方法
        Solution062 solution062 = new Solution062();
        int result1 = solution062.uniquePaths(m1,n1);
        int result2 = solution062.uniquePaths(m2,n2);
    
        // 判断期望值与实际值
        Assert.assertEquals(expResult1, result1);
        Assert.assertEquals(expResult2, result2);
    
    }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan