Dynamic Programming §

It is an optimization over plain recursion. If there is a recursive solution that has repeated calls for same inputs, it can be optimized using Dynamic Programming.

This simple optimization reduces the time complexities from exponential to polynomial.

The two main properties of a problem that suggests Dynamic Programming can be applied on it are:

---

1. Overlapping Subproblems §

Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems. It is mainly used when solutions to subproblems are needed again and again. Here, computed solutions to subproblems are stored in a table so that these don’t have to be recomputed.

There are 2 ways of storing the results of subproblems

Memoization (Top Down)

• A lookup array with all values as NIL is initialized
• Whenever we need a solution to a subproblem, we first look into the lookup table
• If precomputed value is there then it is returned, otherwise, the value is calculated and stored in the lookup table
• Table is filled on demand

Tabulation (Bottom Up)

• It builds the table in a bottom-up fashion and returns the last entry from the table
• Table is filled from the first entry till last

---

2. Optimal Substructure §

A problem has an Optimal Substructure property if optimal solution of the problems can be obtained by using optimal solutions of its subproblems.

For example, shortest path in a graph, If a node x lies in the shortest path from a source node a to destination node b , then the shortest path from a to b is the combination of shortest path from a to x and shortest path from x to b

Memoization Recipe §

1. Make it work §

• visualize the problem as a tree
• implement the tree using recursion
• test it

2. Make it efficient §

• add a memo object (cache)
• add a base case to return memo values
• store return values into the memo

Tabulation Recipe §

• visualize the problem as a table
• size of the table depends on the inputs
• initialize the table with default values
• seed the trivial answer into the table
• iterate through the table
• fill further positions based on the current position