Dynamic programming is an important algorithm paradigm that decomposes a problem into a series of smaller subproblems and avoids redundant calculations by storing the solutions to the subproblems, thereby greatly improving time efficiency.
Characteristics of Dynamic Programming Problems#
Subproblem decomposition is a common algorithmic approach, with different focuses in divide and conquer, dynamic programming, and backtracking.
- The divide and conquer algorithm recursively divides the problem into multiple independent subproblems until the smallest subproblem is reached, and merges the solutions to the subproblems in backtracking to obtain the solution to the original problem.
- Dynamic programming also recursively decomposes the problem, but the main difference from the divide and conquer algorithm is that the subproblems in dynamic programming are interdependent, and many overlapping subproblems occur during the decomposition process.
- The backtracking algorithm exhaustively tries and backtracks to explore all possible solutions, and avoids unnecessary search branches through pruning. The solution to the original problem consists of a series of decision steps, and we can consider each subsequence before each decision step as a subproblem.
Dynamic programming is commonly used to solve optimization problems. They not only involve overlapping subproblems, but also have two other characteristics: optimal substructure and no aftereffect. - Definition of optimal substructure: The optimal solution to the original problem is built from the optimal solutions to the subproblems.
- No aftereffect: Given a certain state, its future development only depends on the current state, regardless of all past states.
Approach to Solving Dynamic Programming Problems#
Consider the following two questions:
- How to determine if a problem is a dynamic programming problem?
- Where to start solving a dynamic programming problem and what are the complete steps?
Problem Determination#
If a problem contains overlapping subproblems, optimal substructure, and satisfies the no aftereffect property, then it is usually suitable for solving with dynamic programming.
Usually, we relax the conditions and first observe if the problem is suitable for solving with backtracking. Problems suitable for solving with backtracking usually satisfy the "decision tree model", where such problems can be described using a tree structure, with each node representing a decision and each path representing a sequence of decisions.
In other words, if a problem contains explicit decision concepts and the solution is generated through a series of decisions, then it satisfies the decision tree model and can usually be solved using backtracking.
On this basis, dynamic programming problems also have some "bonus points" for determination:
- The problem involves descriptions of maximum or minimum values, or maximum or minimum occurrences.
- The problem's state can be represented using a list, multidimensional matrix, or tree, and there is a recursive relationship between a state and its surrounding states.
There are also some "deduction points": - The goal of the problem is to find all possible solutions, rather than finding the optimal solution.
- The problem description has obvious permutation and combination characteristics, requiring the return of specific multiple solutions.
Problem Solving Steps#
The solving process of dynamic programming varies depending on the nature and difficulty of the problem, but usually follows the following steps: describe the decision, define the state, build the dp table, derive the state transition equation, determine the boundary conditions, etc.