This is indeed a DP problem. Now, to answer your question why, we would first begin with a brute-force approach as with any other DP problem and later on realise that the problem contains Overlapping Subproblems and Optimal Substructure.

So, first thing first, let us try to solve this using recursion. The problem states that we want to have more heads than tails, so we want all the possible permutations and combinations where `number-of-heads > N/2`

. Now, think about how would you solve this naively using recursion? Give it thought for a moment and come back. If you are stuck then proceed below.

Say, for example, we have a function `f(n, K)`

which can count the probability of getting K heads using last n coins only, now we start with the coin number 1, and for this coin, and for any coin in general we have two choices - either make it a head or make it tail. Let us suppose for convenience that we currently are at the index i, and so, as per the question the probability of getting a head here is p_{i}(read as p subscript i) (oops! can we use Latex in Markdown? Anybody let me know if we can), so the recursion from the next will proceed as follows(assume 1 based indexing instead of 0)-

p_{i} * f(n - i, K - (heads_selected_so_far + 1)) -> select a head here

+

(1 - p_{i}) * f(n - i, K - (heads_selected_so_far)) -> select a tail here

Now, do you see repeated branches of computation here? No? Draw the recursion tree on a plain sheet of paper and you will(with enough practice you don’t even need to do that) :).

Now, once you realise that this question indeed has computations we can memoize we, we simply add all the results for getting head > `N/2`

using all the coins, that is to say, if we have N coins in total and that `dp[i][j]`

represents the probability of getting j heads using first i coins then we add `dp[N][N/2 + 1] + dp[N][N/2 + 2] + ... + dp[N][N]`

to the answer.

Now, how to do the bottom-up? It is not very hard from here(if you understood everything till here) and if you have tried some problems on DP previously(such as LCS) then it shouldn’t be much tough. I will leave it on you to try to that for the moment, if you are still stuck fill free to ask me.