IntermediateMath for DSADynamic Programming
Choosing k of n: nCr and Pascal's triangle
C(n, k) = n! / (k!(n−k)!) counts ways to choose. Unique Paths on an m×n grid is C(m+n−2, m−1): no DP needed.
The idea
C(n, k) is the number of ways to pick k items out of n when order doesn't matter. C(5, 2) = 10: the 10 pairs from 5 people.
Pascal's rule, C(n, k) = C(n−1, k−1) + C(n−1, k), says “either item n is picked or it isn't”, which is exactly a DP recurrence. Many grid and choice problems are secretly this formula.
Worked example
Unique Paths in a 3 × 7 grid (only right or down)
- Every path is 2 downs and 6 rights: 8 moves in total.
- A path is decided by which 2 of the 8 moves are downs.
- C(8, 2) = 8 × 7 / 2 = 28 paths.
In code (Python)
def n_choose_k(n, k):
k = min(k, n - k)
result = 1
for i in range(1, k + 1):
result = result * (n - k + i) // i # stays an integer at every step
return result
def unique_paths(m, n):
return n_choose_k(m + n - 2, m - 1)O(k) multiplications.
How to spot it
- “number of ways to choose / arrange”, lattice paths on a grid, rows of Pascal's triangle.
Common mistakes
- Computing n! first: huge numbers (and overflow outside Python).
- Mixing up combinations (order doesn't matter) and permutations (it does).
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →