Two Perspectives of Dynamic Programming Enumeration
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 115. Distinct Subsequences | 🔴 |
Prerequisites
Before reading this article, you should first learn:
In this article, we will review a series of problem-solving techniques related to dynamic programming and then focus on discussing the issue of different perspectives during brute-force in dynamic programming.
Dynamic Programming Problem-Solving Techniques
Firstly, as mentioned in My Algorithm Practice Notes, the essence of algorithm problems we practice is "brute-force," and dynamic programming problems are no exception. You must find a way to exhaust all possible solutions and then filter out the solutions that meet the requirements.
Moreover, during the brute-force process of dynamic programming problems, overlapping subproblems may lead to redundant calculations. Therefore, the previous article Dynamic Programming Core Techniques Framework explains how to optimize the brute-force solution into a more efficient dynamic programming solution step by step.
However, writing a brute-force solution requires a state transition equation, which is the core of solving dynamic programming problems and is not easy to conceive. The previous article Dynamic Programming Design: Mathematical Induction guides you on a basic method to think about state transition equations, which is mathematical induction. This involves clearly defining the dp function or array and then using this definition to deduce unknown "states" from known "states."
The focus of this article is the issue that even if the definition of the dp function/array is the same, if you use different "perspectives" to perform brute-force, the efficiency may not be the same.
Regarding the issue of brute-force "perspectives," the previous article Ball and Box Model: Two Perspectives of Backtracking discussed how different brute-force perspectives in backtracking algorithms lead to different solutions. This perspective shift also exists in dynamic programming problems. The example of permutations in the previous article greatly aids in understanding the issue of brute-force perspectives, and we will briefly mention it here again.