1
在一個電子遊戲中，有N個關卡，每個關卡都需要你有一定的能量才能贏得這個關卡。你以0能量開始等級0的遊戲，每當你贏得一個等級時，你消耗的等級需要的能量（你的能量不能低於0）。另外，每個級別都有0,1個或更多商店，以成本C銷售能量E，如果發現自己沒有足夠的能量通過某個級別，則會失去原因，因爲您無法轉到先前的級別從其他商店購買。無論何時從商店購買，您的新能源消費量都是E（商店銷售的商品），也就是說，它不會與您以前的能源總和。如何解決這個優化問題？
問題：贏得所有N級所需的最低資金是多少？ （假設金錢是無限的，你可以購買你想要的所有商店，但是我想優化它，以便它只購買必要的）
我很想知道如何找到解決方案。解決這類問題的解決問題的技術是否可以解釋？是否有類似的已知問題，我應該先學習？
我嘗試使用遞歸回溯，希望找到重疊的狀態並使用動態編程，但我沒有找到它們。我的國家在哪裏：對於所有商店，分叉兩個分店......購買商店，或者不購買。
這在結構上看起來與8皇后問題類似，這是使用回溯深度第一次搜索解決的，但它似乎已經嘗試過了。我不會在每個商店分支（購買或不購買），因爲從同一級別的多個商店購買不會給我帶來任何好處，因爲能量不會相加。我認爲一個好主意是購買能夠讓你跳到下一個級別的最低能量，如果在任何時候你被困在一個級別，回溯併購買更高的能量。 –