Treasure Map

This problem specifies how much gold mines produce each day, and how long it takes to get between them. It then asks what the maximum gold you can collect is. Caveats include you can only collect the gold produced on the day you arrive, and you cannot stay at a mine for consecutive days.

While this sounds convoluted, we realize that one of the caveats is nice. The fact that we can only collect the day's gold at a given mine means that every day can be examined independently, giving us a perfect dp subproblem:

dp[mine][day] = maximum amount of gold that can be collected when starting at mine on day.

Given that we must terminate within 1000 days (since all mines must stop producing gold), the array size is 1 million. The graph is sparse (e ~= v), so the number of edges amortizes away, and we can recurse on each possible path from a given node, and the algorithm is still fast enough.