Two Perspectives of Dynamic Programming Enumeration
Note
Now all the plugins has supported English. I'm still improving the website...
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 115. Distinct Subsequences | 🔴 |
Prerequisites
Before reading this article, you should first learn:
In this article, I will guide you through a review of various problem-solving techniques for dynamic programming questions, with a focus on discussing different perspectives in exhaustive enumeration for dynamic programming.
Dynamic Programming Problem-Solving Combo
Firstly, as mentioned in the previous article My Problem-Solving Insights, the essence of the algorithm problems we solve is "exhaustive enumeration." Dynamic programming problems are no exception; you must find a way to enumerate all possible solutions and then filter out those that meet the problem's requirements.
Additionally, during the exhaustive process of dynamic programming, overlapping subproblems can lead to redundant calculations. Therefore, the previous article Dynamic Programming Core Framework explains how to gradually optimize a brute-force enumeration approach into a more efficient dynamic programming solution.
However, writing a brute-force solution requires a state transition equation, which is the core of solving dynamic programming problems and not so easy to come up with. Nonetheless, the previous article Dynamic Programming Design: Mathematical Induction tells you that a basic method for thinking about state transition equations is mathematical induction. This involves clearly defining the dp function or array and then using this definition to derive unknown "states" from known ones.
The main focus of this article is the following issue: even if the definition of the dp function/array is the same, using different "perspectives" for exhaustive enumeration may not yield the same efficiency.
Regarding the issue of "perspectives" in exhaustive enumeration, the previous article Ball and Box Model: Two Perspectives of Backtracking Exhaustion discussed how different perspectives in backtracking algorithms lead to different solutions. This shift in perspective also exists in dynamic programming problems. The example of permutations in the previous article is very helpful for understanding the issue of enumeration perspectives, and I will briefly mention it again here.