Problem
The binomial coefficent C(n, k) can be recursively defined as follows. C(n, k) = C(n - 1, k - 1) + C(n - 1, k) for all integers n ≥ 0 and k such that 1 ≤ k ≤ n = 1 when k = 0 or k = n Design a dynamic programming algorithm that given n and k, computes C(n, k) based on the above formula (thus does not use any multiplication). You should present a pseudocode for the algorithm and analyze its time complexity.