动态规划和回溯算法的思维转换
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 139. Word Break | 🟠 |
| 140. Word Break II | 🔴 |
Prerequisites
Before reading this article, you should first learn:
Previously, Hand-Holding Guide to Binary Trees (Overview) divided recursive exhaustion into two approaches: "Traversal" and "Problem Decomposition". The "Traversal" approach can be extended to backtracking algorithms, while the "Problem Decomposition" approach can be expanded into dynamic programming algorithms.
In Hand-Holding Guide to Binary Trees (Strategies), I provided examples of some binary tree problems, offering solutions using both "Traversal" and "Problem Decomposition" approaches. This helps you understand more advanced algorithm design ideas through binary trees.
Of course, this kind of thinking is not limited to binary tree-related algorithms. In this article, we will step out of binary tree problems and see how to abstract real algorithmic problems into tree structures, thus applying "Traversal" and "Problem Decomposition" thinking. This allows a smooth transition from Backtracking Algorithms to Dynamic Programming Algorithms.
To digress a bit, the previous article Dynamic Programming Core Framework Explained mentioned that standard dynamic programming problems always seek the optimal value. This is because dynamic programming problems have a property called "optimal substructure," meaning the optimal solution to the original problem can be derived from the optimal solutions of its subproblems.
However, in everyday language, even if a problem is not about finding the optimal value, as long as it uses memoization to eliminate overlapping subproblems, we generally call it a dynamic programming algorithm. Strictly speaking, this does not fit the definition of dynamic programming problems. Calling such a solution a "DFS algorithm with memoization" might be more accurate. But let's not get too caught up in these terminological details. Since it's commonly referred to as dynamic programming, we might as well use that term.
The two problems discussed in this article are not about finding the optimal value, but we will still refer to their solutions as dynamic programming solutions. I wanted to clarify this detail upfront to avoid any confusion for attentive readers. Without further ado, let's dive into the problems.