Home

#About

Welcome to the coconut_delivery wiki!

This was a coding challenge completed which I assume was designed to test knowledge of dynamic programming. This Wiki will help explain the approach I took to the problem.

#Algorithmic Model

I build & maintain an array storing the minimum cost to get to the end of the jetstream at the index. I will call this array minCostArray. jetstreams is a list of jetstreams ordered by their end points.

jetstreams ...

minCostArray ...

#Building minCostArray

In building the minCostArray, there are a few cases we must consider.

1. Using the current jetstream
   1. Walk from the beginning to the current jetstream before using it
   2. Walk from any of the previous jetstreams. That jetstream must end before the current one starts.
2. Not using the current jetstream. We walk from any of the previous jetstreams. Those jetstreams must end before the current one ends.

#Complexity

minCostArray is linear in the number of jetstreams. From the cases we see in building this array, we find the complexity is linear in finding the minimum cost in using previous jetstreams in the worst case. As a result, our algorithm is quadratic.

The answer in getting to the end point with minimal cost is simply the last value in minCostArray once we are done building it.