Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Triangle
Bookmark
Input
Example 1
Example 2
Example 3
Custom
triangle
=
[[2],[3,4],[6,5,7],[4,1,8,3]]
rows =
4
2
3
4
6
5
7
4
1
8
3
0
1
2
3
step down to an adjacent cell each row; build cheapest totals bottom-up
rows =
4
2
3
4
6
5
7
4
1
8
3
0
1
2
3
step down to an adjacent cell each row; build cheapest totals bottom-up
rows =
4
2
3
4
6
5
7
4
4
1
1
8
3
0
1
2
row = 3
dp[3][1] = triangle[3][1] =
1
the path ends here
rows =
4
2
3
4
6
5
7
4
4
1
1
8
8
3
0
1
2
row = 3
dp[3][2] = triangle[3][2] =
8
the path ends here
rows =
4
2
3
4
6
5
7
4
4
1
1
8
8
3
3
0
1
3
row = 2
row 2
each cell adds the cheaper of its two children
rows =
4
2
3
4
7
6
5
7
4
4
1
1
8
8
3
3
0
1
3
row = 2
6
+ min(
4
,
1
) = 6 +
1
=
7
rows =
4
2
3
4
7
6
6
5
10
7
4
4
1
1
8
8
3
3
0
1
3
row = 2
7
+ min(
8
,
3
) = 7 +
3
=
10
rows =
4
2
3
4
7
6
6
5
10
7
4
4
1
1
8
8
3
3
0
2
3
row = 1
row 1
each cell adds the cheaper of its two children
rows =
4
2
9
3
10
4
7
6
6
5
10
7
4
4
1
1
8
8
3
3
0
2
3
row = 1
4
+ min(
6
,
10
) = 4 +
6
=
10
rows =
4
2
9
3
10
4
7
6
6
5
10
7
4
4
1
1
8
8
3
3
1
2
3
row = 0
row 0
each cell adds the cheaper of its two children
rows =
4
answer
11
2
9
3
10
4
7
6
6
5
10
7
4
4
1
1
8
8
3
3
0
1
2
3
min total =
11
= 2 + 3 + 5 + 1
algo
master
.
io
Step:
Walk top to bottom, each step moves to an adjacent cell below. Build the cheapest totals from the bottom up
0 / 14
Input
Example 1
Example 2
Example 3
Custom
triangle
=
[[2],[3,4],[6,5,7],[4,1,8,3]]
0 / 14
algo
master
.
io
Step:
Walk top to bottom, each step moves to an adjacent cell below. Build the cheapest totals from the bottom up
