# Minimum expected cost through an unconventional graph with probabilities at which edges are selected

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.

Problem Structure
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).

Example:

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").


All 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).

Question

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?

• Seems like dynamic programming still works even with the 20% chance to skip a room. Why do you think that prevents you from solving it? What difficulty are you having with modelling that part? – D.W. Jan 16 '18 at 7:01
• I've been building the table bottom-up and having difficulty with expected cost for rooms 2&3. With challenge 1 min cost is x. With challenge 2, I'm paying more for room 2 each time I arrive there but might be reaching room 3 cheaper. I could consider the cost of room 3 using the minimum of challenge 1 from room 2 and challenge 2 successes on room 1, but ideally I'd want to consider the value of achieving room 2 in the 4/5 that don't achieve room 3. I think I should lower cost of room 3 (when calculated as 5 successful challenge 2s on room 1), but I see negative costs when reducing by 4x. – bdean20 Jan 17 '18 at 1:06

In other words, let $A[r,b]$ denote the probability of success when starting at room $r$ and starting with budget $b$, using the optimal strategy. Given $A[r+1,\cdot]$, you can compute $A[r,\cdot]$ via a simple recurrence (consider all possible things you could buy, and the probability of beating room $r$, and how much that reduces your budget when starting at room $r+1$). This immediately leads to a dynamic programming algorithm for your problem.
If charms persist from one room to the next, use $A[r,b,c]$ where $c$ is the set of charms you already have when you start at room $r$.