title: How to calculate expected number of turns using DP in O(n)?
body: <p>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:</p>
  <ol>
  <li>You start on the leftmost cell.</li>
  <li>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.</li>
  <li>You win once you exit the board i.e., you win when your index j &gt; n.</li>
  </ol>
  <p>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.</p>
  <p>How to calculate the expected number of turns needed to win using dynamic programming algorithm that runs in time (n) for the above game?</p>