I did it using dp. dp[i] = probability that Roger wins in 'i' or less tosses. dp[i]= dp[i-1] + when he wins in exactly 'i' tosses
The second term above means that the last three tosses have got to be THH or else he would have won in less than 'i' tosses which has already been counted in dp[i-1] . So the second term would mean (1-dp[i-3])*1/2 * 1/2 * 1/2 . Now the probability that Dave wins for any 'i' would be (1-dp[i]). -- Dipit Grover B.Tech in Computer Science and Engineering - lllrd year IIT Roorkee, India -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
