# How to calculate the minimum price required to buy all the stones?

I have shared the question above. My current algorithm does the calculation in O((n^4)*(2^n)). Can someone please help me out to solve this faster?

• Please credit the original source where you encountered this task. – D.W. Jul 18 '20 at 17:58
• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! – D.W. Jul 18 '20 at 17:58
• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercise- or contest-style tasks for you is unlikely to achieve that. You might find this page helpful in improving your question. See also our resources for how to approach dynamic programming problems: cs.stackexchange.com/tags/dynamic-programming/info -- I suggest you try that approach, then edit the question to show your progress so far. – D.W. Jul 18 '20 at 17:58
• I think you have good intentions D.W. but I'm not a student trying to get the community to solve my homework! Secondly, you just asked generic questions rather than giving me a simple hint towards the correct answer. As far as the image thing is concerned, I agree 100% so I would be making edits to the question to make the entire thing text. For sources, my friend sent this image to me with no further question so I have no sources to append. If I find any sources I would attach it in the future. – Goku Africa Jul 18 '20 at 19:49

The optimal solution will always have the following form: You will change the types of the stones t times, at a total cost of tx. And for each type, you buy the stone when it is cheapest.

Let's say t = 3, so you changed the types three times. To get a stone of type 7, for example, you could have bought the 7th stone immediately, the 6th stone after one change, the 5th stone after two changes, or the 4th stone after three changes, so you obviously buy the cheapest of stones 4 to 7 when it has type 7.

Let prev (i, t) be the index of the stone that will have type i after t changes. Obviously prev (i, 0) = i, and prev (i, t+1) = prev (i, t) - 1 if prev (i, t) ≠ 1, and prev (i, t+1) = n if prev (i, t) = 1.

Let cost (i, t) be the minimum cost to buy a stone of type i if t changes are made. Obviously cost (i, 0) = $$a_i$$, and cost (i, t+1) = min (cost (i, t), $$a_{prev (i, t+1)}$$).

Let cost (t) be the minimum cost to buy a stone of each type if t changes are made. This is obviously t*x + the sum of cost (i, t) over all i. You pick t such that cost (t) is minimal, and the solution will be found in $$O (n^2)$$ steps.