I am not able to memoise it, i tried , but giving me wrong ans

#1
#2

I don’t code in java but since this is a fairly simple dp I can help .
Take a look at this c++ code https://ide.codingblocks.com/s/287401

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.

#3

ya fine , actually i tried with other method, like putting head or tail at position , then when reaching at index n , checking if head>tail , then add probability in ans

#4

its giving ac for some test cases but runtime for other

#5

ya but yours sol pretty good too and easy one :\ …thanks btw .

#6

still i want to know , why its giving runtime??

#7
#8

my solution is here , memory given is 1024 mb , and time 2 sec

#9

You aren’t allowed an array of this much size actually so in case of bigger n you get runtime error.

Rule of thumb is

when n is of the order of 10^5, it’s going to be 1-d Dp or maybe second dimension is something small then. (like a dp[10^5][100])

when n is of the order of 10^3 it’s probably 2-d Dp ( solution having n^2 complexity) or a bigger state dp with other dimensions small.

and when n is lower than that then you can start thinking of something like dp[n][n][n]

#10

woah cool , thanks :slight_smile:

#11

one more thing , what should be the constraints so that recursion + memoisation would not give stack overflow ??

#12

Usually if you are allowed an array of that size you can solve it recursively.

For example if it’s a 2-d Dp , and you are allowed to declare an array of that size, lets say dp[n][n].
Then you can probably solve it recursively because in the worst case you should be calculating n^2 values of the table.

#13

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.