Introduction to Dynamic Programming

Definition

Dynamic programming is a method of solving problems simplifying a problem by breaking it down into related sub-problems solving in a recursive manner, like the Fibonacci Sequence.

F(n) = \begin{cases} 0 & \text{if } n = 0, \\ 1 & \text{if } n = 1, \\ F(n-1) + F(n-2), & \text{if } n \ge 2. \end{cases}

Optimal Substructure

Every DP problem has an optimal substructure. This means that the optimal solution to the overall problem can be constructed by combining optimal solutions to its subproblems.

Example (of optimal substructures)

Fibonacci Sequence

Base Cases: $F(0) = 0$ and $F(1) = 1$ .
Recurrence Relation: $F(n) = F(n-1) + F(n-2)$

To find the optimal value of $F(n)$ , we must first find the optimal values of the two smaller subproblems, $F(n-1)$ and $F(n-2)$ .

Floyd–Warshall All-Pairs Shortest Path Algorithm

This algorithm relies on the idea that any shortest path has a shortest substructure.

Intuition: The shortest path from node $i$ to $j$ using only intermediate nodes from the set $\{1, 2, \dots, k\}$ is denoted $d_k[i][j]$ .
Recurrence Relation: $d_k[i][j] = \min\big( \underbrace{d_{k-1}[i][j]}_{\text{Path does NOT use } k}; \quad \underbrace{d_{k-1}[i][k] + d_{k-1}[k][j]}_{\text{Path DOES use } k} \big)$

This recurrence shows that the best path is built by comparing two options: the current best path, or a new path composed of two smaller subpaths (shortest path from $i$ to $k$ and shortest path from $k$ to $j$ ), all of which were previously solved optimally in the $(k-1)$ iteration.

Explaining this algorithm is out of scope here, so for a walkthrough you can refer to the video: Floyd Warshall All Pairs Shortest Path Algorithm | Graph Theory | Dynamic Programming.)*

Overlapping Subproblems

A DP-friendly problem repeatedly solves the same subproblems instead of generating new ones. This can be solved through memoization, but it’s a common characteristic of these algorithms.

Example (of overlapping subproblems)

Fibonacci Sequence

Using the Fibonacci recursive formula, we repeat calculations:

1
F(5) = F(4) + F(3)
2
F(4) = F(3) + F(2)
3
F(3) = F(2) + F(1)
4
...

Remark

Overlapping Subproblems is different than the dividing and conquering approach of Merge Sort. It divides into subproblems but they don’t overlap.

Top-down with memoization implementation

The strategy used for the fibonacci example is called top-down. This is because we start the computation from the top of the problem (the n-th position) and recursively move downward to smaller subproblems. Once the base cases are reached, we combine the results as the recursion unwinds back toward the top.

1
public HashMap<Integer, Integer> cache = new HashMap<>();
2

3
public int fib(int n) {
4
   if (n < 2) return n;
5
   if (cache.containsKey(n)) return cache.get(n); // Memoization to avoid re-calculations
6
   int result = fib(n - 1) + fib(n - 2);
7
   cache.put(n, result);
8
   return result;
9
}

Bottom-up with tabulation implementation

Think about the smallest subproblems and iteratively build up to the solution, adding the solutions of each subproblem in an array, getting the last item as the result.

Returning to the Fibonacci example, when you want to have the N number of the sequence, the smallest subproblem is to get the 1st number of the sequence (after 0 and 1)

1
int[] sequence = new int[3]
2
sequence[0] = 0;
3
sequence[1] = 1;
4
// 1st number fib(n)
5
sequence[2] = sequence[1] + sequence[0];

Now repeat the solution of the subproblem for the next steps with a loop while storing past results in your tabulation array:

1
int[] sequence = new int[N + 1]
2
sequence[0] = 0;
3
sequence[1] = 1;
4

5
for (int i = 2; i <= N; i++) {
6
  sequence[i] = sequence[i - 1] + sequence[i - 2];
7
}
8

9
int result = sequence[N]

Tip

Since only the last 2 numbers are necessary, It’s possible to remove this tabulation array to make this function O(1) in space, just replace it with 2 variables.

1
int previous = 0;
2
int current = 1;
3

4
for (int i = 2; i <= N; i++) {
5
  int temp = current;
6
  current = previous + current;
7
  previous = temp;
8
}
9

10
return current;

Going from here…

Solve leetcode problems by filtering for the dynamic programming tag, the algomap.io/roadmap is a good source for this. Good for me (and for you, if you’re reading this)