I want to know my mistake

#1

https://ide.codingblocks.com/s/269673

#2

https://atcoder.jp/contests/dp/tasks/dp_i link of question

#3

return ans only when i==n and count>=(n+1)/2
you are returning answer as soon as count is more than half which is incorrect!

#4


still not getting the corect answer.
when i removed the memorization part in this code i got the correct answer.

#5

You need to change the states!
because current state is [coin_index][head_count], now it can’t differentiate between
H,T,H and T,H,H as for both cases coin_index and head_count is same!
Take states as [coin_index][tails_allowed]. Try to implement it.

#6

still same

#7

in the code
/*if(dp[i][count]>-0.9){
return dp[i][count];
}
*/ if i’ll removw this part then it works fine

#8

See this works now https://ide.codingblocks.com/s/270542
don’t pass answer (as it potentially accounts as another state, making DP work incorrectly)

1 Like
#9

ohk i got my mistake .thanks. one more thing , can u explain how to convert this in bottom up dp

#10

For bottom up just fill the dp with base case,
then apply same recurrence iteratively!

#11

i am not able to figure it out .please help me out

#12


Please see it! I made bottom up from your top down code only!

#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.