[問題] cutting sticks

[mqazz1 (無法顯示)]

suppose that we cut a stick of length L (a positive integer) with the

probability P at each position such that its distance from the left end

is a positive integer.

design an efficient dynamic programming algorithm for calculating the

probability that a stick of length at least n remains.

我手中的答案是

令F(k,n)為把長度k的木棒 切出有一條長度至少為n木棒的機率

        F(k,n) = 0,     if 1<=k<=n-1

        F(k,n) = 2PF(k-1,n) + (1-P)^(k-1),      if k>=n

請問這個式子是怎麼導出來的?

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.228.24.240
推 suhorng:2*p*f(k-1,n): 最左邊切一刀或最右邊切一刀, 用剩下的k-1
→ suhorng:長木棍切出n長
→ suhorng:(1-p)^{k-1}: 這k-1個間隔都不切,剩下長度自然也≧n
→ suhorng:是說這遞迴式看起來好怪...真的是對的嗎 ?
→ mqazz1:不清楚耶 因為這是別人解的 請問s大會怎麼寫呢?
→ FRAXIS:或許是(1-P)^(k-1) ?