# 动态规划穷举的两种视角

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

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.