I'm having trouble identifying the approach to minimize the cost of reaching a certain state in an optimization problem. I've modeled it here as a game.
You buy heroes and send them into a dungeon consisting of rooms containing each two challenges (random number check with a given threshold per room) that each hero can choose between (one hero completing a challenge does not allow another to skip it). The goal is to have any hero survive to the final room, and the secondary goal is to minimize the cost for doing so.
The first challenge costs a small fixed amount and success leads that hero to the next room (other heroes must complete their own challenges). The second challenge costs a medium fixed amount and if the challenge is successful, he rolls a fair 5-sided die. Anything below a 5 will move the hero to the next room. A 5 will move the hero 2 rooms ahead.
Failure on any challenge leads to the hero's death unless "divine protection" has been bought for this attempt at the chosen challenge (can only be used in the first two rooms). You can also buy a "charms" for your hero that will improve chances of success for a single attempt by various factors (1.5x, 2x, etc).
All heroes cost 300g. The 1.5x charm costs 650g. The 2x charm costs 1100g. The 2.5x charm costs 2100g (but this can't be used at the same time as protection). Divine protection for room 1 costs 2000g per challenge. Divine protection for room 2 costs 4500g per challenge. In the first room, challenge 1 costs 120g and has 40.5% success before charms. In the first room, challenge 2 costs 210g (has same success rates but also 20% of successes move 2 rooms). In the second room, challenge 1 costs 140g and has 13.5% success. In the second room, challenge 2 costs 230g. In the third room, challenge 1 costs 160g and has 10.% success. In the third room, challenge 2 costs 250g. In the forth room, challenge 1 costs 180g and has 4.1% success. In the forth room, challenge 2 costs 270g. In the fifth room, challenge 1 costs 300g and has 2.7% success. In the fifth room, challenge 2 costs 390g. The sixth room is the final room ("you win the game").
g values can change due to market fluctuations, but I'm looking to solve the optimization problem for any snapshot in time (where we can say the costs are 'fixed' while we're calculating, but we'll have to plug the numbers in again the next time we calculate).
Without the 20% chance on successes to skip a room, it can be modeled as a dynamic programming problem, but I haven't been able to figure out an approach to make that work.
What kind of approach would be appropriate for minimizing the expected cost of putting a hero in a given room?