问题描述:
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?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
原问题链接:https://leetcode.com/problems/unique-paths/
问题分析
这个问题比较有意思,因为它从一开始看机器人的移动位置的时候,有点不太好找到思路。要解决这个问题,需要充分利用问题里提到的一个限制条件,就是机器人每次只能考虑向左或者向下移动。这样,我们要求它所有可能的移动路径时,就需要结合这个条件进行计算推导。
我们可以首先从最简单的形式来考虑,对于1 x 1的矩阵来说,它的起始节点和终止节点就是在一个点上,可以认为是1。而对于2 x 2的矩阵来说呢,对于节点[0][1]来说,它只能有一种选择,也就是说它到终点的路径数是1,对于[1][0]来说也一样。而对于[0][0]来说,它可以向下也可以向右移动,所以它的路径的数量等于它左边节点和它下面节点的路径数的和。也就是path(i, j) = path(i + 1, j) + path(i, j + 1); 所以我们就得到了路径数计算的推导关系。
另外,具体看矩阵,它的最后一行和最后一列所有的点其实就只有一种路径。这些可以作为初始条件。然后我们可以根据前面的path推导条件循环往前递推。这过程有点像动态规划的思路。我们从matrix[i - 2][j - 2]开始,每次一行或者一列的去计算当前位置的值,直到最后的matrix[0][0]。
这样,我们可以得到如下的代码实现:
public class Solution { public int uniquePaths(int m, int n) { if(m <= 1 || n <= 1) return 1; int[][] matrix = new int[m][n]; for(int i = 0; i < n; i++) matrix[m - 1][i] = 1; for(int i = 0; i < m; i++) matrix[i][n - 1] = 1; for(int i = m - 2; i >= 0; i--) { for(int j = n - 2; j >= 0; j--) matrix[i][j] = matrix[i + 1][j] + matrix[i][j + 1]; } return matrix[0][0]; } }
相关推荐
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 Java Associated Documents and Resources Peter norvig神牛Python代码写的很飘逸,果然是有LISP...
leetcode 答案 leetcode 08/18 Unique Paths 应该是简单的数学排列组合问题,提炼一下其实就一句话:有m个黑球,n个白球,有多少种不同的排列方式。 我数学太差,没找到答案,直接上了动态规划。 Unique Paths II ...
例如,"Unique Paths" (题号 62) 需要计算一个机器人到达目标位置的路径数量。 8. **深度优先搜索 (DFS)** 和 **广度优先搜索 (BFS)**:这两种搜索算法常用于解决各种问题,如迷宫求解、岛屿计数等。 9. **排序和...
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
【描述】"leetcode63" 提到的这个问题,全称为“Unique Paths II”,是LeetCode中的一个经典问题。在这个问题中,任务是计算一个机器人从左上角到达右下角有多少种不同的路径。与标准的“Unique Paths”问题相比,...
扩展矩阵leetcode ...uniquePaths 63.不同路径II uniquePathsWithObstacles 139.单词拆分 wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75.颜色分类 sortColors 179.最大数 largestNumber 324.摆
leetcode 530 力码 全部的: 易(173/237+x) 中(144/437+x) 硬(4/x) 问题 1.Two Sum(dict) 7.(跳过)(数学) 9.(跳过)(串串技巧) 11.盛水最多的容器 12.(跳过)(问题不好) 13.(跳过)(蛮力) 14.(跳过)...
javascript js_leetcode题解之62-unique-paths.js
javascript js_leetcode题解之63-unique-paths-ii.js
1、记忆化 2、二维dp 3、滚动优化
unique_paths.py(类似于 chess_board.c!)+ unique_paths2.py chess_board.c 效率测试 bin_search.py 素数.py 零知识.py Leetcode:现在很多小方案都是leetcode,我主要是为了好玩。 著名算法:Knuth-Morris-Pratt...
43. Unique Paths:机器人在一个 m x n 的网格中从左上角移动到右下角,有多少不同的路径。 44. Unique Paths II:与 Unique Paths 类似,但是考虑网格中障碍物的处理。 45. Maximum Sum Subarray:找出一个数字序列...
63.Unique Paths II 64.最小路径和 70.爬楼梯 72.编辑距离 122. 买卖股票的最佳时机 II 152.最大积子阵列 198.强盗 322.硬币变化 贪心算法 45.跳跃游戏II 55.跳跃游戏 哈希 1.二和 3.最长不重复字符的子串 49.组字谜...
- **Unique Paths**:计算机器人到达目标位置的唯一路径数。 - **Maximum Subarray**:寻找数组中的最大子数组和。 - **Climbing Stairs**:模拟爬楼梯,每次可以爬1阶或2阶。 5. **回溯(Backtracking)**: -...
- Unique Paths / Unique Paths II: 前者计算从矩阵的左上角到右下角的路径数量;后者则考虑了障碍物。 - Minimum Path Sum: 在一个m×n的网格中,找到从左上角到右下角的路径,使得路径上的数字总和最小。 - Plus ...
Unique Paths 这道题是一道动态规划的题,还算简单。状态转移方程为: path[i][j] = path[i-1][j] + path[i][j-1]; i和j表示的是i*j的网格从左上角到右下角的路径数量。 并且初始的时候path[i][j]都为1。 为方便起见...
* Unique Paths:给定一个矩形,返回从左上角到右下角的路径数量。这个题目需要使用动态规划的思想,将矩形分解成更小的子矩形,并统计路径数量。 * Maximum Subarray:给定一个数组,返回数组中的最大子数组和。这...
62.unique-paths.cpp [TODO] 5. 最长回文子串.cpp 第 3 天: [TODO] 96.unique-binary-search-trees.cpp [TODO] 70. 爬楼梯.cpp [TODO] 746. min-cost-climbing-stairs.cpp 第 4 天: [待办事项] leetcode/1143。 ...
例如,"Unique Paths"(不同路径)和"House Robber"(打家劫舍)都是经典的动态规划题目。 3. **回溯与深度优先搜索**:这类算法通常用于解决组合优化问题和图遍历问题。例如,"N-Queens"(八皇后问题)和"Word ...