> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/dynamic_programming/game-dp/biased-coins-k-heads.md).

# 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)`