A backgammon player will be playing three consecutive matches with friends tonight. For each match, he will have the opportunity to place an even bet that he will win; the amount bet can be any quantity of his choice between zero and the amount of money he still has left after the bets on the preceding matches. For each match, the probability is ½ that he will win the match and thus win the amount bet, whereas the probability is ½ that he will lose the match and thus lose the amount bet. He will begin with $75, and his goal is to have $100 at the end. (Because these are friendly matches, he does not want to end up with more than $100.) Therefore, he wants to find the optimal betting policy (including all ties) that maximizes the probability that he will have exactly $100 after the three matches.
Use dynamic programming to solve this problem.