1
在一个电子游戏中，有N个关卡，每个关卡都需要你有一定的能量才能赢得这个关卡。你以0能量开始等级0的游戏，每当你赢得一个等级时，你消耗的等级需要的能量（你的能量不能低于0）。另外，每个级别都有0,1个或更多商店，以成本C销售能量E，如果发现自己没有足够的能量通过某个级别，则会失去原因，因为您无法转到先前的级别从其他商店购买。无论何时从商店购买，您的新能源消费量都是E（商店销售的商品），也就是说，它不会与您以前的能源总和。如何解决这个优化问题？
问题：赢得所有N级所需的最低资金是多少？ （假设金钱是无限的，你可以购买你想要的所有商店，但是我想优化它，以便它只购买必要的）
我很想知道如何找到解决方案。解决这类问题的解决问题的技术是否可以解释？是否有类似的已知问题，我应该先学习？
我尝试使用递归回溯，希望找到重叠的状态并使用动态编程，但我没有找到它们。我的国家在哪里：对于所有商店，分叉两个分店......购买商店，或者不购买。
这在结构上看起来与8皇后问题类似，这是使用回溯深度第一次搜索解决的，但它似乎已经尝试过了。我不会在每个商店分支（购买或不购买），因为从同一级别的多个商店购买不会给我带来任何好处，因为能量不会相加。我认为一个好主意是购买能够让你跳到下一个级别的最低能量，如果在任何时候你被困在一个级别，回溯并购买更高的能量。 –