Balance Beam

To save money for a new stall in her barn, Bessie the cow has started performing in the local circus, demonstrating her remarkable sense of balance as she carefully walks back and forth on an elevated balance beam!

The amount of money Bessie earns for her performance depends on where she eventually jumps off the beam. The positions on the beam are labeled $0$, $1$, $\dots$, n + 1 from left to right. If Bessie ever reaches position $0$ or n + 1, she falls off one of the ends of the beam and, sadly, receives no payment.

When Bessie is at position $k$, she can do one of the following:

1. Flip a coin. If it comes up tails, she moves to position k - 1; if it comes up heads, she moves to position k + 1 (that is, each outcome occurs with probability $1/2$).

2. Jump off the beam and receive a payment of f(k)~(0 \le f(k) \le 10^9).

Bessie realizes that she cannot guarantee any particular payment, since her movement is governed by random coin flips. However, for each starting position, she wants to determine her expected payment if she makes an optimal sequence of decisions (that is, decisions that lead to the highest possible expected payment). For example, if her strategy earns her a payment of $10$ with probability $1/2$, $8$ with probability $1/4$, and $0$ with probability $1/4$, then her expected payment is the weighted average 10 \cdot (1/2) + 8 \cdot (1/4) + 0 \cdot (1/4) = 7.