PROBLEM LINK: Exploring Undiscovered Planets
AUTHOR: tds115
DIFFICULTY: Easy-Medium
PREREQUISITES: DP, Heaps
The recurrence relation of the following problem can be defined as f(n)=a[n]+min( f(n-1),f(n-2),...,f(n-k)), where a[i] is the value of petrol per litre.
We can use the memorization technique to solve the following, to get minimum of last k elements we can maintain a heap.
Expected Solution - Dkil7V - Online Java Compiler & Debugging Tool - Ideone.com.
Any similar problem…
Thanks
There is a whole class of problems on this topic. Key-word is “Gas Station Problem”. There are many variations.
Thanks a lot…
No problem
Can someone explain the code or process in easier manner.
Thanks
It can also be done using deque and approach similar to sliding-window problems
Can u share your apraoch pls…
My approach was this:
for every planet a[i], we need to go to that planet from a[i+1] to a[i+k+1] with the minimum weight/cost “to the end”
to calculate the weight “to the end” we start from last and memoize the results
let n be 8 and k be 3 then the dependency would look like this
so we start from the last and then maintain a priority_queue/multiset for the next k elements and remove them once we are past k elements O(NlgK )
(OR)
a deque for O(N)
my code here
Amazing, thanks you very much for explaining your method