How to calculate expected number of turns using DP in O(n)?

Question

A single-player board game. The board is made up of a row of n cells numbered 1 to n from left to right. Cell ‘j' contains a positive integer cj. The rules are like this:

1. You start on the leftmost cell.
2. On each turn, you roll a fair 6-sided die with A as the outcome number. You move forward A × cj cells, where j is the index of the cell that you are standing on.
3. You win once you exit the board i.e., you win when your index j > n.

For instance, consider the board of size n=10 To begin with, you are at the first cell having the value c1 = 2. In the first turn, you roll a dice and obtain a value 1, so you move forward 2 cells. Then on the next roll you roll a 5 on cell 3 (with c3 = 4), so you move forward 20 cells makes you exit the board. You win!! You took 2 turns to win.

How to calculate the expected number of turns needed to win using dynamic programming algorithm that runs in time (n) for the above game?

Answer 1

The recurrence relation you're looking for is:

E[j] = 0 (if j > n)
E[j] = 1 + 1/6 * sum_k(E[j + k * c_j]) (otherwise, for k \in 1..6)