Leetcode 62. Unique Paths & 63. Unique Paths II

简介: 原谅我重新贴一遍题目描述,不是为了凑字数,而是为了让搜索引擎能索引到这篇文章,其实也是算一种简单的SEO。 简单描述下题目,有个机器人要从左上角的格子走到右下角的格子,机器人只能向下或者向右走,总共有多少种可能的路径?

好久没刷题了,今天来俩道简单题。


Leetcode 62. Unique Paths

Leetcode 63. Unique Paths II


A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?


 原谅我重新贴一遍题目描述,不是为了凑字数,而是为了让搜索引擎能索引到这篇文章,其实也是算一种简单的SEO。

 简单描述下题目,有个机器人要从左上角的格子走到右下角的格子,机器人只能向下或者向右走,总共有多少种可能的路径?

 第二题和第一题唯一的不同是第二题多了一些限制,有些格子不能走,但其实这并未增加题目的复杂度。俩道题有个共同的解题方式——动态规划。 关键思路是 到每个格子的路径数只和这个格子左边和上边格子的有关,是到左和上边格子的路径数之和。 用代码描述就是 obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]; 恩,第二题的核心代码就这一行,剩下的就是对初始状态、特殊格子和边界的处理,完整代码如下,仅供参考。


public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        for (int i = 0; i < obstacleGrid.length; i++) {
            for (int j = 0; j < obstacleGrid[0].length; j++) {
                if (1 == obstacleGrid[i][j]) {  //特殊格子处理
                    obstacleGrid[i][j] = 0;
                    continue;
                }
                if (0 == i + j) {  //左上角格子,初始状态处理
                    obstacleGrid[i][j] = 1; 
                    continue;
                } else if (0 == i) {   //上边界处理
                    obstacleGrid[i][j] = obstacleGrid[i][j - 1];
                } else if (0 == j) {   //左边界处理
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j];
                } else {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                }
            }
        }
        return obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1];
    }
}

 第62题也可以用同样的方式解决,但是需要自己创建一个m*n的数组。此解法的时间复杂度O(m*n) 空间复杂度同是O(m*n)。但其实这道题可以用组合数学的方式解决,可以把空间复杂度降到O(1)。

 机器人从左上角走到右下角,总共需要走m+n-2步,向下走了m-1步,向右走n-1步。 这不就变成一个(m+n-2)中选(m-1)或(n-1)的组合数问题了吗? 如此代码就可以变的非常简短了。

public class Solution {
    public int uniquePaths(int m, int n) {
        int N = n + m - 2;
        int k = m - 1; 
        double res = 1;
        for (int i = 1; i <= k; i++)
            res = res * (N - k + i) / i;
        return (int)res;
    }
} 

 很遗憾的是因为63题中引入了特殊情况,无法再用数学的方式处理了,貌似只能用DP(反正我是没想到方法)。

目录
相关文章
LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
LeetCode 257. Binary Tree Paths
给定一个二叉树,返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。
57 0
LeetCode 257. Binary Tree Paths
|
机器人
LeetCode 63. Unique Paths II
机器人位于m x n网格的左上角(在下图中标记为“开始”)。 机器人只能在任何时间点向下或向右移动。 机器人正试图到达网格的右下角(在下图中标记为“完成”)。 现在考虑是否在网格中添加了一些障碍。 有多少条独特的路径?
98 0
LeetCode 63. Unique Paths II
|
机器人
LeetCode 62. Unique Paths
机器人位于m x n网格的左上角(在上图中标记为“开始”)。 机器人只能在任何时间点向下或向右移动。 机器人正试图到达网格的右下角(在下图中标记为“完成”)。 有多少可能的独特路径?
80 0
LeetCode 62. Unique Paths
|
算法 机器人 人工智能