Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Maximum Number of Points with Cost
Bookmark
Input
Example 1
Larger Matrix
Equal Values
Single Column
Custom
points
=
[[1,2,3],[1,5,1],[3,1,1]]
grid =
3x3
1
2
3
1
5
1
3
1
1
dp
left
right
pick one cell per row; every column switch costs the distance
grid =
3x3
1
2
3
1
5
1
3
1
1
dp
left
right
pick one cell per row; every column switch costs the distance
grid =
3x3
1
2
3
1
5
1
3
1
1
row = 1
dp
1
2
3
left
1
right
j = 0
left[0] = dp[0] =
1
the relay starts here
grid =
3x3
1
2
3
1
5
1
3
1
1
row = 1
dp
1
2
3
left
1
2
3
right
3
j = 2
right[2] = dp[2] =
3
the mirror relay starts here
grid =
3x3
1
2
3
1
5
1
3
1
1
row = 1
dp
1
2
3
left
1
2
3
right
1
2
3
combine: dp[j] = points[1][j] + max(
left[j]
,
right[j]
)
grid =
3x3
1
2
3
1
5
1
3
1
1
row = 1
dp
2
7
4
left
1
2
3
right
1
2
3
j = 2
1
+ max(
3
,
3
) =
4
grid =
3x3
1
2
3
1
5
1
3
1
1
row = 2
dp
2
7
4
left
right
row 2
best reachable total for every column?
grid =
3x3
1
2
3
1
5
1
3
1
1
row = 2
dp
2
7
4
left
2
7
6
right
-1
j = 2
left[2] = max(
6
,
4
) =
6
the relay carries on
grid =
3x3
1
2
3
1
5
1
3
1
1
row = 2
dp
2
7
4
left
2
7
6
right
6
7
4
-1
j = 0
right[0] = max(
6
,
2
) =
6
the relay carries on
grid =
3x3
1
2
3
1
5
1
3
1
1
row = 2
dp
9
8
4
left
2
7
6
right
6
7
4
j = 1
1
+ max(
7
,
7
) =
8
grid =
3x3
1
2
3
1
5
1
3
1
1
-1
dp
9
8
7
left
right
max points =
9
= (2 + 5 + 3) - 1 move
algo
master
.
io
Step:
Pick one cell per row. Switching columns between rows costs the distance moved
0 / 26
Input
Example 1
Larger Matrix
Equal Values
Single Column
Custom
points
=
[[1,2,3],[1,5,1],[3,1,1]]
0 / 26
algo
master
.
io
Step:
Pick one cell per row. Switching columns between rows costs the distance moved
