A dynamic programming table stores solutions to overlapping subproblems so larger solutions can reuse them instead of recomputing them. Its entries represent problem states, while transitions define relationships between states. section 4.2.4 section 4.5
Construct a dynamic programming table by:
- Defining the states represented by table entries. section 4.2.4
- Specifying base cases and recursive transitions between states. section 4.2.4
- Populating entries top-down as needed with memoization or bottom-up from the smallest subproblems. section 4.2.4
- Reading the final solution from the required table entry. section 4.2.4
Binomial coefficients
For C(n, k), overlapping recursive calls are stored in a table. With n = 5 and k = 2, top-down computation memoizes encountered entries, while bottom-up computation fills entries from base cases; both require O(nk) time and space. 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))
Compare recursive memoization with iterative table construction in the binomial-coefficient implementation. section 4.2.4
