How does one solve this optimization?
<p>In a videogame, there are N levels, each one requires you to have a certain amount of energy in order to win that level. You start the game at level 0 with 0 energy, and every time you win a level, you spend the energy the level requires (your energy can't go below 0). Also each level has 0, 1, or more shops that sells energy amount E at cost C. If you find yourself without enough energy to pass a level, you lose because you can't go to previous levels to buy from other shops. Whenever you buy from a shop, your new amount of energy is E (the one the shop sells), that is, it doesn't sum up to your previous energy.</p>

<p>The question: What is the minimum money necessary in order to win all N levels? (assuming money is infinite and you can buy all shops you want,... but I want to optimize it so that it buys only the necessary)</p>

<p>I'm interested to know how does one finds the solution for this. Are any problem solving technique that solves this kind of problems, if so, can you explain?. Are there similar known problems that I should study first?</p>

<p>I tried using recursive backtracking, with the hope of finding overlapping states and use dynamic programming, but I didn't find them. My states where: for all shops, fork two branches... buys the shop, or doesn't.</p>