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://blog.csdn.net/cmqwan

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

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

最后

以上就是勤恳指甲油为你收集整理的Leetcode算法Java全解答--62. 不同路径Leetcode算法Java全解答–62. 不同路径的全部内容，希望文章能够帮你解决Leetcode算法Java全解答--62. 不同路径Leetcode算法Java全解答–62. 不同路径所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。