赞
踩
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
∙ \bullet ∙
示例 1
:
输入:m = 3, n = 7
输出:28
∙ \bullet ∙
示例 2
:
输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
∙ \bullet ∙
示例 3
:
输入:m = 7, n = 3
输出:28
∙ \bullet ∙
示例 4
:
输入:m = 3, n = 3
输出:6
提示
:
∙
\bullet
∙ 1 <= m, n <= 100
∙
\bullet
∙ 题目数据保证答案小于等于 2 * 109
来源:力扣(LeetCode)
链接:题目来源
∙ \bullet ∙ 我们生成一个与网格等大的数组dp,dp[i,j] 表示机器到到达 (i,j) 的不同路径数,最后返回 dp[m-1][n-1]。
∙ \bullet ∙ 对于第一行和第一列来说,每个网格只有一种方法可以到达,也就是一直向左或者一直向右,所以我们在初始化数组时直接给每个网格初始化为1。
∙
\bullet
∙ 接下来我们就可以从第二行第二列进行数组填充,对于每一个位置(i,j)来说,都可以由左边或者上边到达,那么路径总数也就是左边一格的路径总数加上边一格的路径总数。
d
p
[
i
]
[
j
]
=
d
p
[
i
−
1
]
[
j
]
+
d
p
[
i
]
[
j
−
1
]
dp[i][j] = dp[i-1][j]+dp[i][j-1]
dp[i][j]=dp[i−1][j]+dp[i][j−1]
class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>>dp(m,vector<int>(n,1)); // for(int i=0;i<m;i++) dp[i][0]=1; // for(int i=0;i<n;i++) dp[0][i]=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]; } };
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
∙ \bullet ∙
示例 1
:
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
∙ \bullet ∙
示例 2
:
输入:obstacleGrid = [[0,1],[0,0]]
输出:1
提示
:
∙
\bullet
∙ m == obstacleGrid.length
∙
\bullet
∙ n == obstacleGrid[i].length
∙
\bullet
∙ 1 <= m, n <= 100
∙
\bullet
∙ obstacleGrid[i][j] 为 0 或 1
来源:力扣(LeetCode)
链接:题目来源
∙ \bullet ∙ 同样我们使用与网格等大的数组dp来记录每个位置的路径总数,最后返回dp数组中最后一个元素。
∙ \bullet ∙ 我们首先对数组进行初始化,先将dp数组整体初始化为0。因为第一行和第一列只能向左或者向下到达,所以我们需要单独对其初始化。对于第一行和第一列我们按顺序从前往后进行搜索,如果该位置没有障碍物我们依此置1,当遇到第一个障碍物以后就直接跳出循环,因为后面的位置已经无法到达。
∙ \bullet ∙ 对于其他位置来说,如果没有障碍物,每个位置的路径总数都等于左边的路径总数加上边的路径总数,否则该位置的路径总数就为0,所以状态转移方程为:
d
p
[
i
]
[
j
]
=
{
0
(
o
b
s
t
a
c
l
e
G
r
i
d
[
i
]
[
j
]
=
1
)
dp[i-1][j]+dp[i][j-1]
(
o
b
s
t
a
c
l
e
G
r
i
d
[
i
]
[
j
]
=
0
)
dp[i][j]=
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m=obstacleGrid.size(); int n=obstacleGrid[0].size(); vector<vector<int>>dp(m,vector<int>(n,0)); for(int i=0;i<m;i++) { if(!obstacleGrid[i][0]) dp[i][0]=1; else break; } for(int j=0;j<n;j++) { if(!obstacleGrid[0][j]) dp[0][j]=1; else break; } for(int i=1;i<m;i++) { for(int j=1;j<n;j++) { if(!obstacleGrid[i][j]) dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[m-1][n-1]; } };
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
∙ \bullet ∙
示例 1
:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。
∙ \bullet ∙
示例 2
:
输入:grid = [[1,2,3],[4,5,6]]
输出:12
提示
:
∙
\bullet
∙ m == grid.length
∙
\bullet
∙ n == grid[i].length
∙
\bullet
∙ 1 <= m, n <= 200
∙
\bullet
∙ 0 <= grid[i][j] <= 100
来源:力扣(LeetCode)
链接:题目来源
∙ \bullet ∙ 对于本题,因为每次操作都需要加每个位置的值,所以我们可以直接在原数组上操作来节省空间开支。
∙ \bullet ∙ 同样第一行和第一列是特例,每个位置的值都等于前边路径总和加该位置的值:
{
grid[i][0]+=grid[i-1][0]
(
i
>
=
1
)
grid[0][j]+=grid[0][j-1]
(
j
>
=
1
)
∙
\bullet
∙ 对于其他位置来说,只需要取左边和上边的较小值加上该位置的值即可:
g
r
i
d
[
i
]
[
j
]
+
=
m
i
n
(
g
r
i
d
[
i
−
1
]
[
j
]
,
g
r
i
d
[
i
]
[
j
−
1
]
)
grid[i][j]+=min(grid[i-1][j],grid[i][j-1])
grid[i][j]+=min(grid[i−1][j],grid[i][j−1])
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m=grid.size(); int n=grid[0].size(); for(int i=1;i<m;i++) { grid[i][0]+=grid[i-1][0]; } for(int j=1;j<n;j++) { grid[0][j]+=grid[0][j-1]; } for(int i=1;i<m;i++) { for(int j=1;j<n;j++) { grid[i][j]+=min(grid[i-1][j],grid[i][j-1]); } } return grid[m-1][n-1]; } };
给定一个三角形 triangle ,找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。
∙ \bullet ∙
示例 1
:
输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出:11
解释:如下面简图所示:
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
∙ \bullet ∙
示例 2
:
输入:triangle = [[-10]]
输出:-10
提示
:
∙
\bullet
∙ 1 <= triangle.length <= 200
∙
\bullet
∙ triangle[0].length == 1
∙
\bullet
∙ triangle[i].length == triangle[i - 1].length + 1
∙
\bullet
∙ -104 <= triangle[i][j] <= 104
来源:力扣(LeetCode)
链接:题目分析
∙ \bullet ∙ 首先来看一下题,题中说明了 t r i a n g l e [ i ] [ j ] triangle[i][j] triangle[i][j] 可以由 t r i a n g l e [ i − 1 ] [ j ] triangle[i-1][j] triangle[i−1][j] 和 t r i a n g l e [ i − 1 ] [ j − 1 ] triangle[i-1][j-1] triangle[i−1][j−1] 下移而来,而对于两边的位置,只能由上一个值下移而来。
∙
\bullet
∙ 所以我们对于两边需要特殊处理:
{
triangle[i][0]+=triangle[i-1][0];
triangle[i][i]+=triangle[i-1][i-1];
∙
\bullet
∙ 而对于剩下的位置,只需要去上边两个数的较小值与本身的值相加即可:
t
r
i
a
n
g
l
e
[
i
]
[
j
]
+
=
m
i
n
(
t
r
i
a
n
g
l
e
[
i
−
1
]
[
j
−
1
]
,
t
r
i
a
n
g
l
e
[
i
−
1
]
[
j
]
)
;
triangle[i][j]+=min(triangle[i-1][j-1],triangle[i-1][j]);
triangle[i][j]+=min(triangle[i−1][j−1],triangle[i−1][j]);
∙ \bullet ∙ 最后我们将最后一行中最小的数选出来返回即可。
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int n=triangle.size(); for(int i=1;i<n;i++) { triangle[i][0]+=triangle[i-1][0]; triangle[i][i]+=triangle[i-1][i-1]; for(int j=1;j<i;j++) { triangle[i][j]+=min(triangle[i-1][j-1],triangle[i-1][j]); } } int res=INT_MAX; for(int i=0;i<n;i++) { res=min(res,triangle[n-1][i]); } return res; } };
给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素)。具体来说,位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
∙ \bullet ∙
示例 1
:
输入:matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出:13
解释:下面是两条和最小的下降路径,用加粗标注:
[[2,1,3], [[2,1,3],
[6,5,4], [6,5,4],
[7,8,9]] [7,8,9]]
∙ \bullet ∙
示例 2
:
输入:matrix = [[-19,57],[-40,-5]]
输出:-59
解释:下面是一条和最小的下降路径,用加粗标注:
[[-19,57],
[-40,-5]]
∙ \bullet ∙
示例 3
:
输入:matrix = [[-48]]
输出:-48
提示
:
∙
\bullet
∙ n == matrix.length
∙
\bullet
∙ n == matrix[i].length
∙
\bullet
∙ 1 <= n <= 100
∙
\bullet
∙ -100 <= matrix[i][j] <= 100
来源:力扣(LeetCode)
链接:题目来源
∙ \bullet ∙ 这道题与上一题十分相似,只不过是将三角形,改成了n×n的矩阵, m a t r i x [ i ] [ j ] matrix[i][j] matrix[i][j] 可以由 m a t r i x [ i − 1 ] [ j − 1 ] matrix[i-1][j-1] matrix[i−1][j−1]、 m a t e i x [ i − 1 ] [ j ] mateix[i-1][j] mateix[i−1][j]、 m a t r i x [ i − 1 ] [ j + 1 ] matrix[i-1][j+1] matrix[i−1][j+1] 下移而来,而对于两边的元素只有两个值可以下移。
∙
\bullet
∙ 同样对于两边需要特殊处理:
{
matrix[i][0]+=min(matrix[i-1][0],matrix[i-1][1]);
matrix[i][n-1]+=min(matrix[i-1][n-1],matrix[i-1][n-2]);
∙ \bullet ∙ 对于剩下的元素来说:
m a t r i x [ i ] [ j ] + = m i n ( m a t r i x [ i − 1 ] [ j − 1 ] , m i n ( m a t r i x [ i − 1 ] [ j ] , m a t r i x [ i − 1 ] [ j + 1 ] ) ) ; matrix[i][j]+=min(matrix[i-1][j-1],min(matrix[i-1][j],matrix[i-1][j+1])); matrix[i][j]+=min(matrix[i−1][j−1],min(matrix[i−1][j],matrix[i−1][j+1]));
∙ \bullet ∙ 最后只需要将最后一行中最小值取出返回即可。
class Solution { public: int minFallingPathSum(vector<vector<int>>& matrix) { int n=matrix.size(); for(int i=1;i<n;i++) { matrix[i][0]+=min(matrix[i-1][0],matrix[i-1][1]); matrix[i][n-1]+=min(matrix[i-1][n-1],matrix[i-1][n-2]); for(int j=1;j<n-1;j++) { matrix[i][j]+=min(matrix[i-1][j-1],min(matrix[i-1][j],matrix[i-1][j+1])); } } int res=INT_MAX; for(int i=0;i<n;i++) { res=min(res,matrix[n-1][i]); } return res; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。