Denge Çubuğu

Ahırında yeni bir bölme yapmak için para biriktirmek isteyen Bessie adlı inek, yerel sirkte gösteri yapmaya başlamıştır; yükseltilmiş bir denge çubuğu üzerinde dikkatle ileri geri yürüyerek dikkat çekici denge yeteneğini sergilemektedir!

Bessie'nin gösterisi için kazandığı para miktarı, sonunda çubuktan nereden atladığına bağlıdır. Çubuk üzerindeki konumlar soldan sağa $0$, $1$, $\dots$, n + 1 olarak etiketlenmiştir. Bessie herhangi bir anda $0$ veya n + 1 konumuna ulaşırsa, çubuğun uçlarından birinden düşer ve maalesef hiçbir ödeme alamaz.

Bessie $k$ konumundayken, aşağıdakilerden birini yapabilir:

1. Bir bozuk para atar. Eğer tura gelirse k - 1 konumuna, yazı gelirse k + 1 konumuna hareket eder (yani her sonuç $1/2$ olasılıkla gerçekleşir).

2. Çubuktan atlar ve f(k)~(0 \le f(k) \le 10^9) ödemesini alır.

Bessie, hareketinin rastgele bozuk para atışlarıyla belirlendiğinden, belirli bir ödemeyi garanti edemeyeceğini fark eder. Ancak, her başlangıç konumu için, en iyi kararlar sırasını (yani en yüksek olası beklenen ödemeye yol açan kararları) uyguladığında elde edeceği beklenen ödemeyi belirlemek ister. Örneğin, stratejisi ona $1/2$ olasılıkla $10$, $1/4$ olasılıkla $8$ ve $1/4$ olasılıkla $0$ ödemesi kazandırıyorsa, beklenen ödemesi ağırlıklı ortalama olan 10 \cdot (1/2) + 8 \cdot (1/4) + 0 \cdot (1/4) = 7'dir.