CAN SOMEONE EXPLAIN THE RECURSIVE SOLUTION MENTIONED IN THE VIDEO?

#1

I am having trouble understanding the recursion mentioned in the video. Please let me know how exactly did he come to that recursive formula

#2

Hello @shibangi go through this :
Here dp[x][y] denotes the probability of having x heads in y tosses.

The transition

dp[x][y] = p[y] * solveDp(x - 1, y - 1) + (1.0 - p[y]) * solveDp(x, y - 1);

is pretty straightforward, you can either have head on the current toss so must have come from
dp[x-1][y-1] or you could have had tail at current toss, so you must have come from dp[x][y-1].

In this loop

for (int i = n; i > n / 2; i–) s += solveDp(i, n);

we sum up all the possiblities.

Like I said dp[x][y] denotes the probability of having x heads in y tosses.

Now what are possible ways of reaching this state?
First observation, y-1 tosses must have been done before this.

Now to get x heads in y tosses, there are two ways.

Either you had x-1 heads in y tosses and got the xth head in the yth toss which is denoted by
(probability of getting head on yth toss) (dp[x-1][y-1]),
or
You already had x heads on y-1 tosses and get tail on the current toss which is equal to
(probability of getting tail on yth toss) (dp[x][y-1]).

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

I think instead of using a loop he is passing the

#5

I replied to you in other thread

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.