91影视

In dynamic programming there are all possibilities and more time as compared to greedy programming. and the Dynamic programming approach always gives the accurate or correct answer. In dynamic programming have to compute only distinct function call because as soon as compute and store in one data structure so that after this reuse afterward if it is needed.

Let us suppose P (i,j ) is the probability for A to win the first n games.

Given that, i = Number of match A has won

And j=Number of match B has won

So, there are two conditions they are,

If P (i,j )=1 where i > 0 and j=1 this mean the probability of A to win is 鈥榦ne鈥�.

If P (i,j )=0 where i > 0 and j=1 , this means the probability of A for won is 鈥榸ero鈥�.

Now for rest of the value of 'i' and 'j' then the value of evaluations is,

$\mathrm{p}\left(\mathrm{i},\mathrm{j}\right)=\frac{1}{2}\left(\mathrm{P}\left(\mathrm{i},\mathrm{j}+1\right)+\mathrm{P}\left(\mathrm{i}+1\right)\right)$

After that let P (0,j ) is as zero or one then compare each situation.

$$\begin{gathered} \mathrm{P}\left(0,\mathrm{i}\right)=1\mathrm{and} \\ \mathrm{P}\left(\mathrm{i},1\right)=0 \\ \mathrm{if}\left(\left(\mathrm{n}-\mathrm{j}\right)>0\mathrm{and}\left(\mathrm{n}-\mathrm{i}\right)=0\right) \\ \mathrm{P}\left(\mathrm{n}-\mathrm{i},\mathrm{j}-\mathrm{i}\right)=1 \\ \mathrm{if}\left(\left(\mathrm{n}-\mathrm{j}\right)=0\mathrm{and}\left(\mathrm{n}-\mathrm{i}\right)>1\right) \end{gathered}$$

Here, A will go on to win the match. For example, if i=n-1 and j=n-3 then the probability that A will win the match is $\frac{7}{8}$, since it must win any of the next three games.

$$\begin{gathered} \mathrm{if}\left(\left(\mathrm{n}-\mathrm{i}\right)>1\mathrm{and}\left(\mathrm{n}-\mathrm{j}\right)>1\right) \\ \mathrm{P}\left(\mathrm{n}-\mathrm{i},\mathrm{j}-\mathrm{i}\right)=\frac{1}{2}\left(\mathrm{P}\left(\mathrm{i}-1,\mathrm{j}\right)+\mathrm{P}\left(\mathrm{i},\mathrm{j}-2\right)\right) \\ \mathrm{return}\mathrm{P}\left(\mathrm{n}-\mathrm{i},\mathrm{j}-\mathrm{i}\right) \end{gathered}$$

By approach of dynamic programming for playing a match to see who is the first to win number of games where equally competent and each has fifty percent chance of winning any particular game and the probability that A will go for to win the match an A will go on to win the match. ifi=n-1 and j=n-3 then the probability that A will win and it will take time of O(n) Since, we are playing 鈥榥鈥� times, so our algorithm will trace output of n output. Thus, runtime would be O(n)