Dynamic programming (DP) solves problems by dividing them into smaller, overlapping subproblems, storing each solution, and reading the final result from a table. Unlike divide and conquer, its subproblems are not independent. section 1.5.2 section 4.2.4
Apply DP by making the subproblem structure explicit:
- Define the problem states represented by entries in the DP table. section 4.2.4
- Specify base cases and the recursive relationships or transitions between states. section 4.2.4
- Populate the table top-down with memoization or bottom-up from the smallest subproblems. section 4.2.4
- Reuse stored results instead of recomputing previously encountered subproblems. section 4.2.4
Binomial coefficients
For C(n,k), overlapping recursive calls can be memoized top-down or filled iteratively bottom-up. Both approaches compute C(5,2) in O(nk) time and O(nk) space; top-down stores only needed subproblems, while bottom-up fills the table from base cases. section 4.2.4
Figure 4.2 Binomial coefficient C(5,2) recursion
Trace the overlapping recursion for the binomial coefficient C(5,2). section 4.2.4
Listing 4.4 Binomial coefficients
def binomial_coeffs1(n, k):
#top down DP
if (k == 0 or k == n):
return 1
if (memo[n][k] != -1):
return memo[n][k]
memo[n][k] = binomial_coeffs1(n-1, k-1) + binomial_coeffs1(n-1, k)
return memo[n][k]
def binomial_coeffs2(n, k):
#bottom up DP
for i in range(n+1):
for j in range(min(i,k)+1):
if (j == 0 or j == i):
memo[i][j] = 1
else:
memo[i][j] = memo[i-1][j-1] + memo[i-1][j]
#end if
#end for
#end for
return memo[n][k]
def print_array(memo):
for i in range(len(memo)):
print('\t'.join([str(x) for x in memo[i]]))
if __name__ == "__main__":
n = 5
k = 2
print("top down DP")
memo = [[-1 for i in range(6)] for j in range(6)]
nCk = binomial_coeffs1(n, k)
print_array(memo)
print("C(n={}, k={}) = {}".format(n,k,nCk))
print("bottom up DP")
memo = [[-1 for i in range(6)] for j in range(6)]
nCk = binomial_coeffs2(n, k)
print_array(memo)
print("C(n={}, k={}) = {}".format(n,k,nCk))
Inspect from-scratch Python implementations of top-down memoization and bottom-up table construction. section 4.2.4
