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

Posted by lizhao on 07-09,2019

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

[toc]

题目

一个机器人位于一个 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