binomial coefficient using dp

Topics

• dynamic programming
• combinatorics

The core idea is based on pascal’s triangle, where each entry is the sum of the two entries directly above it.

The algorithm constructs a table C where C[i][j] stores the value of $\left(\genfrac{}{}{0ex}{}{i}{j}\right)$. The base cases are $\left(\genfrac{}{}{0ex}{}{i}{0}\right)=\left(\genfrac{}{}{0ex}{}{i}{i}\right)=1$. The binomial coefficient recursive relation is:

$$\left(\genfrac{}{}{0ex}{}{i}{j}\right)=\left(\genfrac{}{}{0ex}{}{i-1}{j-1}\right)+\left(\genfrac{}{}{0ex}{}{i-1}{j}\right)$$

This relation allows us to build the table row by row, avoiding redundant calculations. The final result, $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, is then found at C[n][r].

def nCr(n, r):
    C = [[0]*(r+1) for _ in range(n+1)]
    for i in range(n+1):
        for j in range(min(i, r)+1):
            if j == 0 or j == i:
                C[i][j] = 1
            else:
                C[i][j] = C[i-1][j-1] + C[i-1][j]
    return C[n][r]

T.C: $O(n^2)$
S.C: $O(n^2)$

Related

• binomial coefficient using factorials