# Most cost effective way to traverse a set path

I have a set path of $$N$$ destinations to be visited in order, knowing the distance $$D_i$$ between each one of them. I can traverse one node $$i$$ with the cost of $$D_i \times r$$ or traverse any $$5$$ nodes in order with a set cost of $$B$$. How can I find the most cost effective way to visit all the destinations using dynamic programming?

• Please edit your question to clarify the problem statement. Can you define more clearly what $D_i$ represents? The distance between node $i$ and what? What do you mean by "any 5 nodes in order"? Can you credit where you encountered this and share the original wording?
– D.W.
Commented Jun 5, 2020 at 20:59
• What have you tried, and what progress have you made? We have general resources on how to approach dynamic programming problems: cs.stackexchange.com/tags/dynamic-programming/info. I suggest you read through those resources, apply the systematic approach listed there, and show us how far you got. Do you have a recursive algorithm? What subproblem decompositions have you tried so far?
– D.W.
Commented Jun 5, 2020 at 21:00
• Is $r$ the same for every node or is it a variable? @BenedictDhm Commented Jun 5, 2020 at 22:07

Let us number the destinations from $$1$$ to $$N$$ and define an array $$c[N]$$ where $$c[i]$$ is the minimum cost to travel to destination $$1 \leq i \leq N$$. We wish to calculate $$c[N]$$.
It is clear that $$c[1] = D_1 \times r$$, because if we find ourselves at destination $$1$$ we can only have gotten there by travelling one destination at a time, instead of travelling five destinations at a time.
The minimum cost of travelling to destination $$2$$ must be $$c[2] = D_2 \times r + c[1]$$ for identical reasons ($$2 < 5$$) as before. We add the minimum cost of reaching destination $$1$$ to the minimum cost of reaching destination $$2$$ because we must have travelled from destination $$1$$ to $$2$$.
Now we see that for destinations $$i \geq 5$$, that we could have reached them by travelling through five destinations at a time instead of the previous one destination at a time. This means $$c[i] = \min(B + c[i - 5], D_{i} \times r + c[i - 1])$$
Where $$c[0] = 0$$. From this pattern, we can calculate $$c[N]$$ in $$O(N)$$ time complexity.