难度中等499收藏分享切换为英文关注反馈
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int uniquePaths(int m, int n) {
int[][] nums =new int[m][n];
for(int[] b: nums ){
Arrays.fill(b, 1);
}
for(int i=1; i< m; i++){
for(int j=1;j<n;j++){
nums[i][j]=nums[i-1][j]+nums[i][j-1];
}
}
return nums[m-1][n-1];
}
}
|
难度中等267收藏分享切换为英文关注反馈
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int row=obstacleGrid.length;
int col=obstacleGrid[0].length;
if(obstacleGrid[0][0]==1){
return 0;
}
obstacleGrid[0][0]=1;
for(int i=1;i<row;i++){
obstacleGrid[i][0]=(obstacleGrid[i][0]==0 && obstacleGrid[i-1][0]==1)? 1:0;
}
for(int j=1;j<col;j++){
obstacleGrid[0][j]=(obstacleGrid[0][j]==0 && obstacleGrid[0][j-1]==1)? 1:0;
}
for(int i=1;i<row;i++){
for(int j=1;j<col;j++){
if(obstacleGrid[i][j]==0){
obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1];
}
else{
obstacleGrid[i][j]=0;
}
}
}
return obstacleGrid[row-1][col-1];
}
}
|
难度中等445收藏分享切换为英文关注反馈
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
1
2
3
4
5
6
7
8
| 输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| class Solution {
public int minPathSum(int[][] grid) {
int row=grid.length;
int col=grid[0].length;
int [][] dp=new int [row][col];
for(int j=col-1;j>=0;j--){
for(int i=row-1; i>=0; i--){
if(i==row-1 && j !=col-1)
dp[i][j]=dp[i][j+1]+grid[i][j];
else if(j==col-1 && i !=row-1)
dp[i][j]=grid[i][j]+dp[i+1][j];
else if(i!=row-1 && j !=col-1)
dp[i][j]=grid[i][j]+Math.min(dp[i+1][j],dp[i][j+1]);
else
dp[i][j]=grid[i][j];
}
}
return dp[0][0];
}
}
Runtime: 3 ms, faster than 24.12% of Java online submissions for Minimum Path Sum.
Memory Usage: 42.6 MB, less than 72.97% of Java online submissions for Minimum Path Sum.
public class Solution {
public int minPathSum(int[][] grid) {
int[] dp = new int[grid[0].length];
for (int i = grid.length - 1; i >= 0; i--) {
for (int j = grid[0].length - 1; j >= 0; j--) {
if(i == grid.length - 1 && j != grid[0].length - 1)
dp[j] = grid[i][j] + dp[j + 1];
else if(j == grid[0].length - 1 && i != grid.length - 1)
dp[j] = grid[i][j] + dp[j];
else if(j != grid[0].length - 1 && i != grid.length - 1)
dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
else
dp[j] = grid[i][j];
}
}
return dp[0];
}
}
Runtime: 2 ms, faster than 85.12% of Java online submissions for Minimum Path Sum.
Memory Usage: 42.1 MB, less than 85.13% of Java online submissions for Minimum Path Sum.
public class Solution {
public int minPathSum(int[][] grid) {
for (int i = grid.length - 1; i >= 0; i--) {
for (int j = grid[0].length - 1; j >= 0; j--) {
if(i == grid.length - 1 && j != grid[0].length - 1)
grid[i][j] = grid[i][j] + grid[i][j + 1];
else if(j == grid[0].length - 1 && i != grid.length - 1)
grid[i][j] = grid[i][j] + grid[i + 1][j];
else if(j != grid[0].length - 1 && i != grid.length - 1)
grid[i][j] = grid[i][j] + Math.min(grid[i + 1][j],grid[i][j + 1]);
}
}
return grid[0][0];
}
}
Runtime: 3 ms, faster than 24.12% of Java online submissions for Minimum Path Sum.
Memory Usage: 42.2 MB, less than 83.78% of Java online submissions for Minimum Path Sum.
|
难度中等365收藏分享切换为英文关注反馈
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
1
2
3
4
5
6
| [
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
|
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int [] n= new int [triangle.size()+1];
for(int i=triangle.size()-1;i>=0;i--){
for(int j=0; j< triangle.get(i).size();j++){
n[j]=Math.min(n[j],n[j+1])+triangle.get(i).get(j);
}
}
return n[0];
}
}
|
难度中等43收藏分享切换为英文关注反馈
给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。
下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
示例：
1
2
3
4
| 输入：[[1,2,3],[4,5,6],[7,8,9]]
输出：12
解释：
可能的下降路径有：
|
[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9][2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9][3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
和最小的下降路径是 [1,4,7]，所以答案是 12。
提示：
1 <= A.length == A[0].length <= 100-100 <= A[i][j] <= 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int minFallingPathSum(int[][] A) {
int m=A.length;
for(int i=m-2;i>=0;i--){
for(int j=0;j<m;j++){
int best=A[i+1][j];
if(j>0)
best=Math.min(A[i+1][j-1],best);
if(j<m-1)
best=Math.min(A[i+1][j+1],best);
A[i][j]+=best;
}
}
int n=Integer.MAX_VALUE;
for(int i:A[0]){
n=Math.min(i,n);
}
return n;
}
}
|
难度困难13收藏分享切换为英文关注反馈
给你一个整数方阵 arr ，定义「非零偏移下降路径」为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
请你返回非零偏移下降路径数字和的最小值。
示例 1：
1
2
3
4
5
6
7
8
| 输入：arr = [[1,2,3],[4,5,6],[7,8,9]]
输出：13
解释：
所有非零偏移下降路径包括：
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。
|
提示：