Dynamic programming is a technique for solving problems, whose solution can be expressed recursively in terms of solutions of overlapping sub-problems. A gentle introduction to this can be found in How Does DP Work? Dynamic Programming Tutorial.

Memoization is an optimization process. In simple terms, we store the intermediate results of the solutions of sub-problems, allowing us to speed up the computation of the overall solution. The improvement can be reduced to an exponential time solution to a polynomial time solution, with an overhead of using additional memory for storing intermediate results.

Let's understand how dynamic programming works with memoization with a simple example.

Analyzing the Recursion Tree: Uncovering the Achilles' Heel

You've seen how the Fibonacci sequence works; now let's peek under the hood. Imagine the Fibonacci sequence as a sprawling tree, where each branch splits into smaller branches until you reach the leaves, which are the base cases.

The Problem of Redundancy

If you study the recursion tree for calculating $f\left(5\right)$, you'll notice something disconcerting. Multiple nodes represent the same Fibonacci number! For example, $f\left(3\right)$ is computed twice, $f\left(2\right)$ is calculated thrice, and the base cases $f\left(1\right)$ and $f\left(0\right)$ appear even more frequently.

Time Complexity: It's Exponential!

Because of this redundancy, our naive recursive approach has a time complexity of $O\left(2^n\right)$. In non-mathematical terms, that means it's slow, especially for larger values of $n$.

The Power of Memoization

Here's the good news: we don't have to live with this inefficiency. By storing the results of computations we've already done, we can avoid redundant calculations. This technique is called memoization, and it's a cornerstone of dynamic programming.

The Road to Optimization

Memoization is like a cheat sheet for your algorithm. It's a simple yet powerful way to remember past results, so you don't have to recalculate them. Here's how it generally works:

Steps to Implement Memoization

1. Create a data structure (usually an array or hash table) to store computed values.
2. Before diving into the recursive calls, check if the result for the current $n$ is already in the storage.
3. If it is, use that value instead of making a new recursive call.
4. If not, proceed with the recursion and store the new result in the data structure.

By doing this, you can dramatically reduce the time complexity from exponential to linear, i.e., $O\left(n\right)$.

From Naive to Smart: Maximizing Grid Rewards

Ah, the grid! Picture it as a treasure map where each cell has its own hidden gem (or, let's say, reward). Our trusty robot wants to navigate this map to find the ultimate treasure—the maximum reward. But there's a catch! The robot can only move up or to the right. How do we make sure our robotic friend picks the richest path?

The Brute-Force Way: Recursive Enumeration

If you've read the tutorial on recursion and backtracking, you know that you can enumerate all paths using backtracking. It's like the robot taking a stroll, noting down each path and the rewards it accumulates.

Steps for Recursive Enumeration

1. Walk through all possible paths while keeping track of the reward for each path.
2. Select the path that garners the maximum reward.

The Downside: Exponential Complexity

This might sound like a simple plan, but it's a costly one. Just like our previous Fibonacci example, this naive approach has an exponential time complexity of $O\left(2^{mn}\right)$. That's a lot of calculations, and our robot doesn't have all day!

Enter Dynamic Programming: A Smarter Approach

Let's switch gears and bring dynamic programming into the picture. Just like we did with the Fibonacci numbers, we can avoid recalculating rewards for the same cell multiple times. This is how dynamic programming turns our robot into a strategic treasure hunter.

Steps to Implement Dynamic Programming

1. Create a 2D array, dp, with dimensions (m \times n).
2. Initialize dp[0][0] with the reward of the starting cell.
3. Loop through the grid, and for each cell (i, j), update dp[i][j] as the maximum reward you can get by either coming from the top cell dp[i-1][j] or the left cell dp[i][j-1], plus the reward at (i, j).
4. The value at dp[m-1][n-1] will be the maximum reward.

By following these steps, we reduce our time complexity from exponential to linear, $O(m\times n)$, which is a significant improvement.

Path Finding with Dynamic Programming

Let's take a step back.

Imagine you're navigating a maze, and each cell in the maze offers you a reward. Your aim is to find the path from the starting point to the destination that maximizes these rewards. This is like a treasure hunt, except you're gathering coins or gems along the way.

The Aha Moment: A Single Principle

Let's crystallize our approach with a powerful observation:

If the richest path passes through a cell at (r, c), then the path leading up to (r, c) and the path leading away from (r, c) to the goal must also be the richest.

Picture it as a road trip where you have multiple stops. If a city along your route is the richest in terms of tourist attractions, the route to that city and beyond must also offer the most attractions.

Breaking Down the Problem

We've essentially divided a big challenge into two smaller tasks:

1. Finding the Richest Path to (r, c): What's the best route from the start to this cell?
2. Finding the Richest Path from (r, c) to Goal: What's the best route from this cell to the destination?

Combine these, and voila, you have your ultimate treasure-rich path.

The Role of Memoization

Just like you'd mark checkpoints on a map, we'll mark the richest path to each cell in a matrix called reward. This matrix will store the maximum accumulated reward from the starting cell to every other cell on the grid.

Two Key Matrices

• Input Matrix $w[r,c]$: This holds the reward for each individual cell at (r, c).
• Memoization Matrix $\text{reward}[r,c]$: This stores the maximum accumulated reward from the start to each cell (r, c).

Think of the first matrix as the list of tourist attractions in each city, and the second matrix as your travel diary, recording the best experiences up to each point.

By the end of this exercise, the cell in reward corresponding to the goal will hold the maximum reward possible. Just follow the path back, and you've solved the maze in the most rewarding way.

Here is the recursive pseudo-code that finds the maximum reward from the start to the goal cell. The pseudo-code finds the maximum possible reward when moving up or right on an m x n grid. Let's assume that the start cell is (0, 0) and the goal cell is (m-1, n-1).

To get an understanding of the working of this algorithm, look at the figure below. It shows the maximum possible reward that can be collected when moving from start cell to any cell. For now, ignore the direction matrix in red.

1Routine: maximizeReward
2Start cell coordinates: (0, 0)
3Goal cell coordinates: (m-1, n-1)
4Input: Reward matrix w of dimensions mxn
5
6Base case 1:
7// for cell[0, 0]
8reward[0, 0] = w[0, 0]
9
10Base case 2:
11// zeroth col.  Can only move up
12reward[r, 0] = reward[r-1, 0] + w[r, 0]  for r=1..m-1
13
14Base case 3:
15// zeroth row.  Can only move right
16reward[0,c] = reward[0, c-1] + w[0, c] for c=1..n-1
17
18Recursive case:
191. for r=1..m-1
20    a. for c=1..n-1
21        i. reward[r,c] = max(reward[r-1, c],reward[r, c-1]) + w[r, c]
222. return reward[m-1, n-1]           // maximum reward at goal state  

Time Complexity of Path Using Dynamic Programming and Memoization

We can see that using matrices for intermediate storage drastically reduces the computation time. The maximizeReward function fills each cell of the matrix only once, so its time complexity is O(m * n). Similarly, the best direction also has a time complexity of O(m * n).

The printPath routine would print the entire path in O(m+n) time. Thus, the overall time complexity of this path finding algorithm is O(m * n). This means we have a drastic reduction in time complexity from O(2${}^{mn}$) to O(m + n). This, of course, comes at a cost of additional storage. We need additional reward and direction matrices of size m * n, making the space complexity O(m * n). The stack of course uses O(m+n) space, so the overall space complexity is O(m * n).

Weighted Interval Scheduling via Dynamic Programming and Memoization

Our last example in exploring the use of memoization and dynamic programming is the weighted interval scheduling problem.

We are given n intervals, each having a start and finish time, and a weight associated with them. Some sets of intervals overlap and some sets do not. The goal is to find a set of non-overlapping intervals to maximize the total weight of the selected intervals. This is a very interesting problem in computer science, as it is used in scheduling CPU tasks, and in manufacturing units to maximize profits and minimize costs.

Problem Parameters

The following are the parameters of the problem:

11. n = total intervals.  We'll use an additional zeroth interval for base case.
22. Each interval has a start time and a finish time.  
3    Hence there are two arrays s and f, both of size (n+1)
4    s[j] < f[j] for j=1..n and s[0] = f[0] = 0
53. Each interval has a weight w, so we have a weight array w.  w[j] >0  for j=1..n and w[0]=0
64. The interval array is sorted according to finish times.

Additionally we need a predecessor array p:

16. p[j] = The non-overlapping interval with highest finish time which is less than f[j].  
2            p[j] is the interval that finishes before p[j]

To find p[j], we only look to the left for the first non-overlapping interval. The figure below shows all the problem parameters.

Scheduling via Dynamic Programming and Memoization

From the recursion tree, we can see that the pseudo-code for running the T function has an exponential time complexity of O(2${}^n$). From the tree, we can see how to optimize our code. There are parameter values for which T is computed more than once-- examples being T(2), T(3), etc. We can make it more efficient by storing all intermediate results and using those results when needed, rather than computing them again and again. Here's the faster version of the pseudo-code, while using an additional array M for memoization of maximum weights up to nth interval.

1# Routine: TFast(j)
2# Input: f, s and w arrays (indices 0..n). Intervals sorted according to finish times
3# Output: Maximum accumulated weight of non-overlapping intervals
4# Intermediate storage: Array M size (n+1) initialized to -1
5def TFast(j):
6    # Base case:
7    if j == 0:
8        M[0] = 0
9        return 0
10
11    # Recursive case:
12    if M[j] != -1:        # if result is stored
13        return M[j]       # return the stored result
14
15    T1 = w[j] + TFast(p[j])
16    T2 = TFast(j-1)
17    M[j] = max(T1, T2)
18
19    return M[j]

`

The great thing about this code is that it would only compute TFast for the required values of j. The tree below is the reduced tree when using memoization. The values are still propagated from leaf to root, but there is a drastic reduction in the size of this tree.

The figure shows the optimal weight array M:

Time Complexity of Weighted Interval Scheduling via Memoization

The time complexity of the memoized version is O(n). It is easy to see that each slot in the array is filled only once. For each element of the array, there are only two values to choose the maximum from-- thus the overall time complexity is O(n). However, we assume that the intervals are already sorted according to their finish times. If we have unsorted intervals, then there is an additional overhead of sorting the intervals, which would require O(n log n) computations.

Well, that's it for now. You can look at the Coin Change problem and Longest Increasing Subsequence for more examples of dynamic programming. I hope you enjoyed this tutorial as much as I did creating it!

One Pager Cheat Sheet

• Dynamic Programming (DP) with Memoization is a technique for optimizing the solution of overlapping sub-problems to anexponential time solutionto apolynomial time solution, while using additional memory to store intermediate results.
• This sentence summarizes the concept of Fibonacci Numbers, which is defined and implemented utilizing a recursive design pattern, wherein each number is the sum of the two preceding numbers in the sequence.
• By examining the recursion tree for computing fibonacci(5), we can deduce an exponential O(2^n) complexity, with potential for speedups by using stored intermediate results.
• We can reduce the exponential time complexity of our Fibonacci computation from O(2^n) to O(n) using a simple memoization technique with only two extra memory spaces.
• Dynamic Programming (DP) is a powerful algorithmic technique used to efficiently solve problems with optimal solutions and overlapping sub-problems through memoization, reducing the complexity from exponential (O(n^2)) to linear (O(n)).
• Finding the path with the highest reward through an m * n grid using Backtracking requires enumerating all possible paths and selecting the one with the maximum reward, resulting in an exponential time complexity of O(2${}^{mn}$).
• By combining the technique of Dynamic Programming with the Memoization of accumulated rewards stored in the reward matrix, we can find the optimum, or best, path from the start to goal that collects the maximum reward.
• The pseudo-code finds the maximum reward when moving up or right on a m x n grid, from (0, 0) to (m-1, n-1).
• The optimal path to a maximum reward can be found by filling an additional matrix d which stores the predecessor for each cell (r, c) when finding the maximum path.
• We can use the direction matrix to backtrack from the goal cell to the start cell and pop the elements off a stack to get the final path.
• Using Dynamic Programming and Memoization, we can drastically reduce the time complexity from O(2${}^{mn}$) to O(m * n), but with a cost of additional storage of O(m * n) space complexity.
• Memoization is a technique which increases space complexity but drastically reduces time complexity, allowing for a significantly faster algorithm.
• The problem parameters given allow us to use dynamic programming and memoization to solve the weighted interval scheduling problem in order to maximize the total weight of the non-overlapping intervals.
• A maximum weight for an interval can be computed recursively by either including or excluding it, and looking at the intervals j-1 and lower for exclusion.
• By using Memoization, we can drastically reduce time complexity and optimize the code efficiency of Dynamic Programming for Scheduling.
• We can retrieve theinterval setusing thepredecessor arraypand theBoolean arrayX`.
• The time complexity of the Memoized version of Weighted Interval Scheduling is O(n), assuming the intervals are already sorted according to their finish times.
• The Longest Increasing Subsequence (LIS) problem using dynamic programming with memoization has a time complexity of O(n^2), achieved by two nested loops of O(n) computations for each of the n slots.
• The space complexity of solving the Longest Increasing Subsequence (LIS) problem using dynamic programming with memoization is O(n).