在电子游戏中，有N个关卡，每个关卡都需要你有一定的能量才能赢得该关卡。你以0的能量从0级开始游戏，每次你赢得一个关卡，你都会花费关卡所需的能量（你的能量不能低于0）。此外，每个级别都有 0、1 或更多商店，以成本 C 出售能量量 E。如果你发现自己没有足够的能量来通过一个关卡，你就输了，因为你无法去以前的关卡从其他商店购买。每当你从商店购买时，你的新能量是E（商店出售的能量），也就是说，它不会和你之前的能量相加。
问题：赢得所有N个级别所需的最低金额是多少？（假设钱是无限的，你可以买下所有你想要的商店,...但我想优化它，以便它只购买必要的）
我很想知道如何找到解决方案。有没有解决问题的技巧可以解决这类问题，如果有，你能解释一下吗？是否有类似的已知问题，我应该首先研究？
我尝试使用递归回溯，希望找到重叠状态并使用动态编程，但我没有找到它们。我的州在哪里：对于所有商店，分叉两个分支...买店，或者不买。
这是一个相当容易的问题，因为能量不求和。这意味着您在 N 级买入后的能量 E（N） 并不取决于您在 0...N-1 级中的表现。这也意味着您可以向后工作;您最后可以购买能量到达终点的商店是什么？对于这些候选人中的每一个，在他们之前的商店中，你必须购买能量才能到达最后一家商店？