Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Minimum Path Sum
Bookmark
Input
Example 1
Example 2
Example 3
Example 4
Custom
grid
=
[[1,3,1],[1,5,1],[4,2,1]]
grid =
3x3
start
end
1
3
1
1
5
1
4
2
1
every step costs its cell; find the cheapest right/down route
grid =
3x3
start
end
1
3
1
1
5
1
4
2
1
every step costs its cell; find the cheapest right/down route
grid =
3x3
start
end
1
1
3
1
1
5
1
4
2
1
dp[0][0]
= grid[0][0] =
1
the route starts here
grid =
3x3
start
end
1
1
3
1
2
1
5
1
6
4
2
1
i = 2
dp[2][0] =
2
+
4
=
6
straight down only
grid =
3x3
start
end
1
1
4
3
1
2
1
5
1
6
4
2
1
j = 1
dp[0][1] =
1
+
3
=
4
straight right only
grid =
3x3
start
end
1
1
4
3
5
1
2
1
5
1
6
4
2
1
j = 2
dp[0][2] =
4
+
1
=
5
straight right only
grid =
3x3
start
end
1
1
4
3
5
1
2
1
7
5
1
6
4
2
1
i = 1
j = 1
min(
4
,
2
) +
5
=
2
+ 5 =
7
grid =
3x3
start
end
1
1
4
3
5
1
2
1
7
5
6
1
6
4
2
1
i = 1
j = 2
min(
5
,
7
) +
1
=
5
+ 1 =
6
grid =
3x3
start
end
1
1
4
3
5
1
2
1
7
5
6
1
6
4
2
1
i = 2
row 2
cheaper of top / left, plus the cell cost
grid =
3x3
start
end
1
1
4
3
5
1
2
1
7
5
6
1
6
4
8
2
7
1
i = 2
j = 2
min(
6
,
8
) +
1
=
6
+ 1 =
7
grid =
3x3
start
end
1
1
4
3
5
1
2
1
7
5
6
1
6
4
8
2
7
1
min path sum =
7
= 1 + 3 + 1 + 1 + 1
algo
master
.
io
Step:
Every cell has a cost. Find the cheapest top-left to bottom-right route, moving only right or down
0 / 12
Input
Example 1
Example 2
Example 3
Example 4
Custom
grid
=
[[1,3,1],[1,5,1],[4,2,1]]
0 / 12
algo
master
.
io
Step:
Every cell has a cost. Find the cheapest top-left to bottom-right route, moving only right or down
