Lets define a function F(int nw, int nb, bool turn) which returns the probability of the princess winning from the state with nw white mouses and nb black mouses currently in the bag and if turn is false it is the princess turn to move and if turn is true it is the Dragon's turn to move.

From this we can see the answer to the original question is F(w, b, false)

First lets take the case where it is the princess's turn to move. For her to win, either she can directly pick a white mouse with probability or she picks a black mouse with probability and for her to win we need to multiply this with F(nw, nb - 1, true). So, the princess's equation is :

Now, lets take the case where it is the Dragon's turn to move. For the princess to win, the Dragon should always pick the black mouse which has probability (nb/(nw+nb)). Now, there can be two cases: the first one is that a white mouse escapes the bag and the second is that a black mouse escapes the bag.

Case 1 : White mouse escapes This happens with probability (-1 because the dragon already picked a black mouse). Now we have to multiply this with F(nw - 1, nb - 1, false) (Since, the dragon picked 1 black mouse and 1 white mouse escaped and 'false' since it will be the princess's turn to move now).

Case 2: Black mouse escapes This happens with probability (Since Dragon already picked a black mouse, there will (nb-1) black mouses left). This should be multipled with F(nw, nb - 2, false) (Since, white mouse remains same and Dragon picked a black mouse and another black mouse escapes).

So, the equation for dragon's move will be:

We can declare an array dp[white][black][turn] to store the results so that it is not computed again. So, the overall complexity would be O(2wb)

We should also handle cases where, nw is 0 or nb is 0 or negative and return appropriate values.

Accepted Solution in C++