Biased Coins K heads

DPV 6.10

Step 1 define subproblems

Want to solve by prefix (aka remove from the end)

What if i don’t have the last $n^{th}$ coin

Two cases

(n-1) have k heads, and nth coin is tail

(n-1) have k-1 heads, and nth coin is head

O(n) number of subproblems

Step 2 Write your recurrence

q(i, j) = q(i-1, j-1) * Pn + q(i-1, j)*(1 -Pn)

Step 3 Write the order of evaluation for memo table

Analysis: we need q(n-1, k-1) and q(n-1, k) before we can compute q(n, k)

Initialization
for all j > i, q(i, j) = 0
for all i = 0, q(i, 0) = 0 // need first row but don’t need first column
// topological order
for (i from 1 to n)
  for (j from 0 to k)    
    q(i, j) = q(i-1, j-1) * Pn + q(i-1, j)*(1 -Pn)

Step 4 desired result

q(n, k)

Step 5 Runtime

#subproblems * time/subprob = O(n) * O(k) = O(nk)