We all know that dynamic programming is a very efficient method for solving problems with repeated subproblems and optimal substructures. Fortunately, many optimization problems exhibit such properties. So today, we mainly want to share how to solve a dynamic programming problem in four steps from algo.monster.
Dynamic programming and divide-and-conquer Algorithm
Let’s start with the difference between dynamic programming and the divide-and-conquer algorithm. The subproblems to be solved by the divide-and-conquer algorithm are independent and can be solved separately. On the other hand, the subproblems to be solved by dynamic programming overlap so that memorization techniques can save the results of the solved problems. Thus, it usually consists of two parts.
- Recursion: solving the subproblems.
- Memorization: saving the computing results.
If you want to know whether a problem is suitable for solving by dynamic programming, you can see whether the problem meets two properties.
Optimal substructure: the optimal solution of the whole problem can be composed of the optimal solution of each subproblem.
Overlapping subproblems: the subproblems will recur.
How to solve dynamic programming problems?
Dynamic Programming (DP) is a methodology for solving specific problems in polynomial time and is much faster than exponential brute force methods. Moreover, we and the system can rigorously prove the correctness.
The four-step to solving dynamic programming problems:
- First, identify whether it is a dynamic programming problem.
- Second, determine the states.
- Third, establish the relationship between the states.
- Fourth, add memos or DP Tables to the states.
The four steps are in detail
Step 1: To determine if a problem belongs to it
In general, problems requiring an optimal solution like the shortest path problem or the longest common subsequence are counting issues that count permutations under certain conditions. So people can easily consider specific probability problems.
All dynamic programming problems satisfy the overlapping subproblem property. And most classical dynamic programming problems also meet the optimal substructure property. Thus, when we find these properties from a given situation, we can determine if dynamic programming can resolve them.
Step 2: Determine the state
The most important aspect of the DP problem is to determine all the states and the transfer equations between the states. Determining the state transfer equations is the hardest part, but it is also fundamental. We must choose the conditions very carefully because the determination of the state transfer equations depends on your choice of the problem state definition. So, what the heck is a state anyway?
A “state” can be thought of as a set of parameters that uniquely identifies the solution of a given subproblem in a given problem. And this set of parameters should be as small as possible to reduce the size of the state space. For example, in the classical Knapsack problem, the state is defined by two parameters, index, and weight, DP[index][weight], and DP[index][weight] denotes the maximum weight that can be obtained by loading the knapsack with items from 0 to index. Thus, the parameters index and weight uniquely determine the solution of a subproblem of the backpacking problem.
So, after determining the given problem, the first step is to assess the state of the problem. Then, the dynamic programming algorithm decomposes the problem into several subproblems. Solve the subproblems first, save the answers to avoid repeated computations, and then obtain the original problem’s solution from the solutions of these subproblems. After determining the state of each subproblem, the next step is to determine the transfer equation from the previous state to the current state, also called the state transfer equation.
Step 3: Construct the state transfer equation
Constructing the state transfer equation is the hardest part of the DP problem and requires sharp enough intuition and observation, both of which are acquired through a lot of practice.
Step 4: Add Memos or DP Tables to the States
A DP table is a bottom-up table created by the dynamic programming algorithm to hold the solution of each subproblem and return the last answer in the table.
It is arguably the most straightforward part. We only need to store the sub-state solutions so that the next time we use a sub-state, we can look it up and get it directly from memory.
Memo vs. DP Table
Using Memo or DP Table can store the re-used subproblem, so which one is better, and how should we choose between the two methods? Draw a period with a question mark.
Although we covered the memoization method in the introduction, the explanation here will be more general. First, let’s look at the way two students learned.
Student 1: To master dynamic programming, I would first study some theory and then practice with many dynamic programming problems.
Student 2: To master the content of dynamic programming, I have to practice some classical emotional programming problems, and for that, I have to study some theory.
Both students are talking about the same thing. The difference is that they pass information in different ways. Student 1 uses a bottom-up approach, while Student 2 uses a top-down approach.
The DP Table is what Student 1 calls a bottom-up approach, and the memo is what Student 2 calls a top-down approach.
Final summary
Steps for solving operative dynamic programming:
Step 1: Determine if a problem is a dynamic programming problem. (Overlapping subproblems, optimal substructures, “they should note most”).
Step 2: Determine the state and its meaning.
Step 3:
- Construct the state transfer equation according to the conditions given in the question.
- Enumerate several sub-states.
- Try to use these sub-states to construct the solution of the unknown state.
You can quickly get the state transfer equation. But, of course, we cannot do this step without a lot of practice).
Step 4: Add a memo or DP Table to the state (there is no absolute good or bad for both) according to personal preference.
Proficiency in this four-step routine, and is there any problem to stop you?
