Dynamic Programming at Five Levels

Level 1: Explanation for a Child

Imagine you are playing a video game and you reach a hard level. Instead of trying to beat it in one go, you figure out how to pass each part of the level separately, and you save your game after each part. The next time you play, you don’t have to start from the beginning, but from where you saved the game last. This way of solving the game, little by little and saving your progress, is similar to what we call dynamic programming in computer science!

Level 2: Explanation for a Teenager

You know when you have a big problem for homework and it seems very hard? But if you break it down into smaller, easier problems, and then use those solutions to solve the big problem, it’s much easier, right? That’s what dynamic programming is like. It’s a method in computer science where we break down a big problem into smaller parts, solve those, and then use the solutions of the small problems to solve the big one.

Level 3: Explanation for an Undergraduate

Dynamic programming is an algorithmic paradigm that solves a complex problem by breaking it into simpler subproblems and storing the results of these subproblems to avoid computing the same results again. It’s used when the problem has the properties of overlapping subproblems and optimal substructure. A classic example is the Fibonacci sequence, where each number is the sum of the two preceding ones. Instead of recalculating overlapping subproblems like in naive recursion, dynamic programming calculates each subproblem only once.

Level 4: Explanation for a Graduate Student

Dynamic programming is a method for solving optimization problems by breaking them down into simpler stages and using the principle of optimality to make decisions at each stage. It’s a powerful technique with applications in a wide variety of fields, from operations research to bioinformatics. Dynamic programming operates by storing the solutions to subproblems in a table so they are only computed once, thereby reducing the exponential complexity in some problem domains to polynomial complexity.

Level 5: Explanation for a Colleague

Dynamic programming is a critical technique in algorithm design, helping us devise polynomial time solutions for problems exhibiting the properties of overlapping subproblems and optimal substructure. By using memoization or tabulation to store intermediate results, dynamic programming eliminates the redundancy in naive recursion, significantly reducing time complexity. Its utility spans various domains, from sequence alignment in bioinformatics to network optimization in operations research. Yet, defining the state and transition function often requires deep insight into the problem at hand.

State and Transition Function

Alright, let’s imagine you’re in a vast city, like New York City, filled with an almost infinite number of intersections. You’re standing at a specific intersection - let’s call this ‘State Street and Main Street’. That’s your current state.

From this state, you can transition to a different state, say by walking to the next intersection - let’s call it ‘State Street and 2nd Street’. The action of moving from your current intersection to the next one is the transition. Each intersection in the city is a different state you can be in, and moving from one to the next is a transition.

Now, consider each of these intersections as a potential situation your computer program might find itself in - each one a unique state. And just like you navigating the streets of the city, the computer program navigates from state to state using transitions.

In a game of chess, for example, the state could be the current layout of the chessboard, and the transition function could be the rules of the game that determine how you can move the pieces. So, in our city analogy, it’s as though you’re playing a game of chess, moving from intersection to intersection, each move changing the state of the game.

So, in simple terms, in computing and mathematics, a state represents a particular condition or circumstance that a system can be in at a given time, and a transition function tells us how we get from one state to another.

Richard Feynman Explanation

Imagine you’re in a big maze with many different paths you can take, and you’re trying to find the quickest way out. Now, you could try every single path, one by one, but that could take a really long time. So, what if, instead, every time you reach an intersection, you make a note of the fastest path to that point?

Then, if you ever come back to that same intersection, you can immediately know the fastest route without having to retrace your steps. This idea, this strategy, is essentially what we call dynamic programming.

You see, in many problems, there are often smaller, overlapping sub-problems. By solving these smaller problems first, and storing their solutions, we can build up the answers to bigger problems. It’s kind of like how, in physics, we often break down complex phenomena into simpler parts to understand them better.

The key to dynamic programming is understanding the structure of these sub-problems and figuring out how to piece together their solutions to solve the bigger problem. It’s not always easy to see the best way to do this, but when you can, it’s a powerful tool that can save a lot of time.

So, in a way, dynamic programming is a bit like having a really good memory when you’re in a maze. It allows you to remember the outcomes of the paths you’ve already explored, so you don’t have to keep exploring them again and again.

Steps

Dynamic Programming is a powerful algorithm design technique that is widely used to solve combinatorial optimization problems. An algorithm that employs this technique is not recursive by itself, but the underlying solution of the problem is usually stated in the form of a recursive function.

Some algorithms break a problem into smaller subproblems and use the solutions of the subproblems to construct the solution of the larger one.

During this process, the number of subproblems may become very large, and some algorithms solve the same subproblem repeatedly, needlessly increasing the running time.

Dynamic programming organizes computations to avoid recomputing values that you already know, which can often save a great deal of time. Examples:

• Fibonacci numbers computed by iteration
• Warshall’s algorithm for transitive closure implemented by iterations
• Floyd’s algorithms for all-pairs shortest paths
• Assembly-line Scheduling
• Matrix-chain Multiplication
• 0/1 Knapsack Problem
• Longest Common Subsequence
• Optimal Binary Tree
• Optimal Polygon Triangulation

Steps for solving:

1. Optimal Substructure: Try to find if there is a recursive relation between problem and subproblem.
2. Write recursive relation of the problem. (Observe Overlapping Sub problems at this step.)
3. Compute the value of sub problems in a bottom up fashion and store this value in some table.
4. Construct the optimal solution from the value stored in step 3.
5. Repeat step 3 and 4 until you get your solution.

Bottom-Up Evaluation

Unlike the case in divide-and-conquer algorithms, immediate implementation of the recurrence results in identical recursive calls that are executed more than once. For this reason, this technique resorts to evaluating the recurrence in a bottom-up manner, saving intermediate results that are used later on to compute the desired solution.

Combinatorial Optimization Problems

Dynamic programming is a general-purpose algorithm design technique that is most often used to solve combinatorial optimization problems, where we are looking for the best possible input to some function chosen from an exponentially large search space.

It is also used to improve the time complexity of the brute-force methods to solve some of the NP-hard problems.

Parts of Dynamic Programming

There are two parts to dynamic programming. The first part is a programming technique: dynamic programming is essentially Divide and Conquer run in reverse: we solve a big instance of a problem by breaking it up recursively into smaller instances; but instead of carrying out the computation recursively from the top down, we start from the bottom with the smallest instances of the problem, solving each increasingly large instance in turn and storing the result in a table.

The second part is a design principle: in building up our table, we are careful always to preserve alternative solutions we may need later, by delaying commitment to particular choices to the extent that we can.

The bottom-up aspect of dynamic programming is most useful when a straightforward recursion would produce many duplicate subproblems. It is most efficient when we can enumerate a class of subproblems that doesn’t include too many extraneous cases that we don’t need for our original problem.

For some of the problems that may be viewed in this way, an optimal sequence of decisions may be found by making the decisions one at a time and never making an erroneous decision.

This is true for all problems solvable by the greedy method. For many other problems, it is not possible to make stepwise decisions (based only on local information) in such a manner that the sequence of decisions made is optimal.

One way to solve problems for which it is not possible to make a sequence of stepwise decisions leading to an optimal decision sequence is to try out all possible decision sequences. We could enumerate all decision sequences and then pick out the best.

Principle of Optimality

In dynamic programming the optimal sequence of decisions is arrived at by making explicit appeal to the Principle of Optimality.

This principle states that an optimal sequence of decisions has the property that whatever the initial state and decision are, the remaining decisions must constitute an optimal decision sequence with regard to the state resulting from the first decision.

Greedy Method vs Dynamic Programming

Thus, the essential difference between the greedy method and dynamic programming is that in the greedy method only one decision sequence is ever generated. In dynamic programming, many decision sequences may be generated. However, sequences containing suboptimal subsequences cannot be optimal (if the principle of optimality holds) and so will not be generated.

An important feature of the dynamic programming approach is that optimal solutions to subproblems are retained so as to avoid recomputing their values. The use of these tabulated values makes it natural to recast the recursive equations into an iterative program.

Problem Requirements

There are two key attributes that a problem must have in order for dynamic programming to be applicable:

• Overlapping Subproblems
• Optimal Substructure

Overlapping Subproblems means that results of smaller versions of the problem are reused multiple times in order to arrive at the solution to the original problem.

Optimal Substructure means that an optimal solution to a problem contains optimal solutions to sub problems.

Dynamic programming uses memoization to maintain a table of sub problems that already been solved. So it reduces the exponential complexity to polynomial complexity (O(n2), O(n3), etc.) for many problems. Memoization means caching.

If the subproblems are independent and there is no repetition in calculation then memoization has no effect, so recursion can be used instead of dynamic programming.

Solution Components

A Dynamic Programming Solution has 2 main components, the State and the Transition

• The State refers to a subproblem of the original problem.
• The Transition is the method to solve a problem based on its subproblems.

The time taken by a Dynamic Programming Solution can be calculated as:

No. of States * Transition Time 

Thus if a solution has N2 states and the transition is O(N), then the solution would take roughly O(N3) time.

Is Dynamic Programming Applicable?

Ask yourself the following questions:

1. Is it possible to divide the problem into subproblems of the same type?

2. Are the subproblems overlapping?

3. Are we optimizing, maximizing or minimizing something or counting the total number of possible ways to do something?

If the answer to the first two questions is yes, Dynamic Programming is applicable. Third question is an additional confirmation.

How to Solve Dynamic Programming Problems

You can solve most of the Dynamic Programming problems by following the below steps:

Step 1 - Check

Check if Dynamic Programming is applicable by asking yourself the three questions.

Step 2 - Define Recursion

• Define problem in terms of subproblems. Define it in a top down manner. Do not worry about time complexity at this point.

• Solve the base case. The subproblems are solved by recursion.

• Add a terminating condition.

After this step, we have a working solution using recursion.

Step 3 - Apply Memoization

If a subproblem is solved multiple times, then cache its solution and use the cached value when same subproblem is encountered again.

Step 4 - Solve Bottom Up.

In this step we eliminate recursion and redefine our solution in forward direction starting from the most basic case. We store only the results that will be required later.

Dynamic Programming Approaches

There are two approaches for solving Dynamic Programming problems:

• Bottom Up Dynamic Programming
• Top Down Dynamic Programming

Bottom Up Dynamic Programming

In this method, we evaluate the function starting with the smallest possible input argument value and then we step through possible values, slowly increasing the input argument value. We store the computed values in a hashtable. As larger arguments are evaluated, pre-computed values for smaller arguments can be used.

Top Down Dynamic Programming

In this method, the problem is broken into sub problems. Each of these sub problems is solved. The solutions are remembered, in case they need to be solved. Also, we save each computed value as the final action of the recursive function. As the first action, we check if pre-computed value exists.

Dynamic Programming Q&A

What are the conditions to choose dynamic programming?

If the following conditions are met, then we can choose Dynamic Programming to solve that problem:

• Recursion - Problem can be solved using the recursive function calls.
• Optimization (min, max, largest) - The problem is requiring some optimizations such as finding Longest Common Sub sequence.
• Choice is given (option to choose something)
• Overlapping subproblems - The solution of one sub problem can be used to find the solution of another subproblem.
• Likely when two recursive calls are made

In Dynamic Programming how to characterize structure of optimal solution?

1. The characterization of optimal solution is given by the optimal substructure of the problem.
2. Optimal substructure of the problem in dynamic programming is the art of the whole problem where the solution of such part will be latter used to find the solution of the whole problem.
3. The subprograms for the optimal solution will be created as such that solution of all those subproblem can be combined to form the whole big solution.
4. Consider the example of find the subset of numbers in a sequence of number such that their sum will be equal to the given below:
5. This problem is dynamic problem where we can divide the problem into subproblems.
6. Each subproblem will be related to either include a particular number in the while sum or not.
7. The solution of this if problem is given by a recursive equation is shown below:

isSubsetSum (set, n, sum) = isSubsetSum (set, n-1, sum) || isSubsetSum (set, n-1, sum-set[n-1])

where isSubsetSum (set, n, sum) will tell that whether the nth number in the sequence will be included in set to which eventually gives the value equal to sum.

Can I use bottom up Dynamic Programming with iterative solution as well as recursive solution? Is bottom up Dynamic Programming used only with iterative solution?

No, you cannot use bottom up Dynamic Programming with iterative solution as well as recursive solution. Yes, bottom up Dynamic Programming is used only with iterative solution. Bottom up dynamic programming works with memoization and iterative approach. For recursive solution, we have to solve the problem top down approach which is also an expensive choice in terms of complexity and stack memory issues. However, it depends upon the type of the problem, dynamic programming can be used by top-down recursive solution and bottom up iterative solution.

Bottom Up Dynamic Programming Algorithm

For example, here is the solution for Fibonacci from MIT class notes:

1
2
3
4
5
6

 fib = {}
 for k in range(1:n+1):
   if k <=2: f = 1
   else: f = fib[k-1] + fib[k-2]
   fib[k] = f
 return fib[n]

Conclusion

The Divide and Conquer, graph exploration, and greedy choice yield definitive algorithms for a variety of important computational tasks. The drawback of these tools is that they can only be used on very specific types of problems.

Revised Version

Dynamic programming and linear programming techniques have a very broad applicability that can be invoked when more specialized methods fail. Predictably, this generality often comes with a cost in efficiency.

Dynamic Programming (DP) is a powerful algorithmic paradigm that solves optimization problems by breaking them into smaller overlapping subproblems, and solving each of those just once. This approach is especially effective when a naive approach would involve solving the same subproblems repeatedly, thereby wasting computational resources. The essential idea is to store the solutions to the subproblems in a table so that they can be reused, or “looked up”, whenever needed again.

Let’s dive a bit deeper into the key concepts:

Overlapping Subproblems

This property is the hallmark of many problems that are suitable for DP. A problem has overlapping subproblems if the problem can be broken down into subproblems which are reused several times.

For instance, in the calculation of the Fibonacci sequence, the subproblem of calculating Fib(n-1) is reused when calculating Fib(n-2). In a naive recursive implementation, this leads to an exponential time complexity because of the repeated calculation of the smaller terms.

Optimal Substructure

A problem has optimal substructure if an optimal solution to the problem can be constructed from optimal solutions to its subproblems. In other words, to solve the problem as a whole, we can first solve its subproblems, use the solutions to these subproblems to solve larger subproblems, and so on. This property allows the solution to be built up from solutions to smaller problems.

The Principle of Optimality

This principle states that an optimal sequence of decisions has the property that, regardless of the initial state and initial decision, the remaining decisions must constitute an optimal sequence with regard to the state resulting from the first decision.

This principle forms the basis for most DP algorithms. Essentially, it implies that we can make optimal decisions one stage at a time. We start at one decision point and move to the next, always making the current decision optimally, with the belief that future decisions will be made optimally as well.

Memoization

Memoization is the technique of storing solutions to subproblems in a table to avoid redundant computations. It’s a common strategy used in DP to optimize the time complexity of the algorithm.

In a top-down DP approach, the algorithm starts by solving the main problem which is then broken down into subproblems. When the solution for a subproblem is found, it is stored in a table. The next time this subproblem needs to be solved, the algorithm simply looks up the solution in the table, rather than re-computing it.

Bottom-Up vs Top-Down DP

In a bottom-up DP approach, the algorithm starts by solving the smallest subproblems and gradually solves larger subproblems using the solutions of the smaller ones. The solution to the largest subproblem then gives the solution to the original problem.

The bottom-up approach is typically iterative and involves filling up a DP table in a systematic manner. This approach does not require recursion and does not involve the overhead of function call stack.

In a top-down DP approach, also known as memoization, the algorithm starts by solving the main problem which it breaks down into subproblems. The solutions to these subproblems are typically stored in a hash table. A top-down approach is usually implemented using recursion, possibly with memoization.

Solving DP Problems

Solving a DP problem typically involves the following steps:

1. Identify if it is a DP problem: The problem must have overlapping subproblems and an optimal substructure to be solved with DP.

2. Decide the state: The “state” can be thought of as the key to a memoization table. It fully captures all necessary information of a subproblem. The state space is the set of all possible states.

3. Formulate a relation among the states: This is also known as the “state transition”,

which describes how a state can be transformed to other states.

4. Define the base cases: The base cases are the smallest subproblems which can be solved directly.

5. Solve in a top-down or bottom-up manner: In top-down (or memoization), the algorithm starts from the main problem and breaks it into subproblems. In bottom-up, the algorithm starts from the smallest subproblem and iteratively solves larger subproblems.

6. Use the memoization table: The memoization table is used to store the results of subproblems to avoid redundant computation.

In conclusion, Dynamic Programming is a powerful tool for solving a wide range of optimization problems. It offers efficient solutions where a brute force or naive recursion strategy would be impractical due to repeated computations. By breaking problems down into overlapping subproblems, and using techniques like memoization and the principle of optimality, dynamic programming allows for elegant, efficient solutions to many complex problems.

Deciding 1D or 2D

How to decide whether a DP problem can be solved with 1 D or 2 D grid?

Choosing between a 1D or 2D dynamic programming solution depends on the nature of the problem and the state representation required to solve it.

A problem can be solved with a 1D dynamic programming grid if the current state only depends on a single previous state. For instance, in the Fibonacci sequence problem, the current state F(n) only depends on the two previous states, F(n-1) and F(n-2), which can be easily stored and updated in a 1D array or even in two variables.

On the other hand, if the current state depends on more than one previous state and these states have to be kept distinct, a 2D (or even 3D or more) grid can be used. For instance, in the problem of finding the longest common subsequence (LCS) of two strings, the state at LCS[i][j] depends on LCS[i-1][j], LCS[i][j-1], and LCS[i-1][j-1], thus needing a 2D grid to maintain all the possible states.

Remember, the dimension of the DP table generally reflects the number of “parameters” in your subproblem definition that can change. If there are two such parameters (e.g., in the LCS problem, where you need to know where you are in both strings), use a 2D table. If there’s only one parameter that changes (like in the Fibonacci problem, where you only need to know what number you’re on), use a 1D table.

However, some problems initially seem like they need a 2D DP table, but you can use clever strategies to reduce them to 1D DP problems by only keeping track of the necessary state. It’s more about how you define your subproblems than the problem itself.

Finally, always analyze the problem and try to understand the nature of its subproblems before deciding on the structure of the DP grid.

Why are you saying states when the number of variables seem determine the decision?

In dynamic programming, the term “state” is often used to describe a scenario that our problem is in, or to represent a specific subset of our problem data. Each state corresponds to a subproblem, and the solution to the main problem is built from the solutions to its subproblems. The variables that define the state are the ones that can change as we move from one subproblem to another.

For instance, if we have a problem where we are trying to find the shortest path from a start point to an end point, the “state” could be the current position. The variables here are the x and y coordinates of the position. This is a case where we would likely use a 2D array for dynamic programming, because there are two variables (x and y coordinates) that can change.

On the other hand, if we were solving a problem where we are trying to compute the nth Fibonacci number, the “state” could be the index n. Here, there is only one variable (n) that changes as we move from one subproblem to another. Hence, we would use a 1D array for dynamic programming.

So, when I say “state”, you can think of it as a particular setting of the variables that define the subproblem. The choice between 1D and 2D (or higher) dynamic programming often depends on the number of variables that define your state and can change as we move from one subproblem to another.

So i, j or x, y are the variables and when they are combined for each value they can take, they are called as a specific state?

Yes, exactly! When solving a problem using dynamic programming, “state” often refers to the collection of variables that define a particular instance of the problem. Each unique set of values these variables can take corresponds to a different state.

For example, in a grid-based path-finding problem, a “state” could be defined by a pair of variables (i, j), where i is the row index and j is the column index of a cell in the grid. Each unique (i, j) pair corresponds to a different cell in the grid, so each state in this problem represents a different cell.

In the context of the problem, the term “state” helps to describe the specific subproblem that you’re considering at any given time. You can think of the process of solving the overall problem as transitioning from one state to another, with the goal of finding the optimal way to reach a final desired state from a given initial state.

Keep in mind that states can be represented using more than just two variables. For more complex problems, states may be defined using three, four, or even more variables. The choice of how many and which variables to use to define the states depends on the specifics of the problem you’re trying to solve.

What are the four steps in developing a dynamic-programming algorithm?

we follow a sequence of four steps:

1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution, typically in a bottom-up fashion.
4. Construct an optimal solution from computed information.