Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Minimum Cost For Tickets
Bookmark
Recursion
Memoization
Calendar DP
Input
Standard
Consecutive
Larger
Custom
days
=
[1, 4, 6, 7, 8, 20]
,
costs
=
[2, 7, 15]
travel days
1
4
6
7
8
20
travel days
1
4
6
7
8
20
travel days
1
4
6
7
8
20
1
4
6
7
8
20
end
$0
end
end
20
end
end
end
end
20
end
end
end
end
20
end
end
end
end
20
end
end
end
end
8
20
end
end
end
20
end
end
end
end
end
7-day pass: $7 then the end of the trip
travel days
1
4
6
7
8
20
1
4
6
7
8
20
$2
end
$0
end
$0
end
$0
20
end
$0
end
end
end
20
end
end
end
end
20
end
end
end
end
20
end
end
end
end
8
20
end
end
end
20
end
end
end
end
end
solve(6): past the last day
travel days
1
4
6
7
8
20
1
4
6
7
8
$4
20
$2
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
end
$0
end
end
end
20
end
end
end
end
20
end
end
end
end
8
20
end
end
end
20
end
end
end
end
end
nothing left to buy
travel days
1
4
6
7
8
20
1
4
6
7
$6
8
$4
20
$2
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
end
end
end
end
20
end
end
end
end
8
20
end
end
end
20
end
end
end
end
end
7-day pass: $7 then day 20
travel days
1
4
6
7
8
20
1
4
6
7
$6
8
$4
20
$2
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
20
end
end
end
end
8
20
end
end
end
20
end
end
end
end
end
solve(6): past the last day
travel days
1
4
6
7
8
20
1
4
6
$8
7
$6
8
$4
20
$2
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
end
$0
end
$0
end
$0
end
8
20
end
end
end
20
end
end
end
end
end
nothing left to buy
travel days
1
4
6
7
8
20
1
4
$9
6
$8
7
$6
8
$4
20
$2
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
8
20
end
$0
end
end
20
end
end
end
end
end
solve(6): past the last day
travel days
1
4
6
7
8
20
1
4
$9
6
$8
7
$6
8
$4
20
$2
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
8
20
$2
end
$0
end
$0
end
$0
20
end
$0
end
$0
end
end
end
nothing left to buy
travel days
1
4
6
7
8
20
1
$11
4
$9
6
$8
7
$6
8
$4
20
$2
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
8
$4
20
$2
end
$0
end
$0
end
$0
20
$2
end
$0
end
$0
end
$0
end
$0
end
$0
cheapest trip costs $11
algo
master
.
io
Step:
Cover 1, 4, 6, 7, 8, 20 for the least money: passes cost $2 (1 day), $7 (7 days), $15 (30 days)
0 / 146
Input
Standard
Consecutive
Larger
Custom
days
=
[1, 4, 6, 7, 8, 20]
,
costs
=
[2, 7, 15]
0 / 146
algo
master
.
io
Step:
Cover 1, 4, 6, 7, 8, 20 for the least money: passes cost $2 (1 day), $7 (7 days), $15 (30 days)
