解锁动态规划的奥秘：从零到精通的创新思维解析（6）
解锁动态规划的奥秘：从零到精通的创新思维解析（6）
前言：
在动态规划的众多问题中，多状态DP问题是一个非常重要的类别。它的难点在于如何设计合适的状态表示和转移方程，从而高效地解决问题。
多状态DP的核心思想在于：针对问题的不同属性或限制条件，将状态表示扩展为多个维度，使得状态可以更加精确地描述问题的子结构。这种方法既可以帮助我们更好地分解问题，又能够在求解过程中保留更多的信息，从而为最终的结果提供完整的支持。
在实际应用中，多状态DP常用于解决路径规划、背包问题、字符串编辑、博弈问题等场景。例如，在路径规划问题中，我们可以通过增加状态的维度来描述位置、步数以及路径的某些限制条件；在资源分配问题中，我们可以通过扩展状态来考虑当前的资源利用率和历史决策。
本篇内容将聚焦于多状态DP问题的基本原理和解决方法，结合典型实例，逐步介绍从状态定义、转移方程设计到代码实现的完整过程。希望通过这一系列讲解，读者能够对多状态DP的理论和实践有更深入的理解，掌握其在解决实际问题时的技巧与方法。
今天小编就要开启动态规划的多状态dp问题的讲解了，希望我讲完几篇文章后，对屏幕后的你会有一定程度的帮助，那么废话不多说，开启今天的做题之旅。
文章目录
- 解锁动态规划的奥秘：从零到精通的创新思维解析（6）
-
- 1.按摩师
-
- 1.1.题目来源
- 1.2.题目分析
- 1.3.思路讲解
-
- 1.状态表示
- 2.状态转换方程
- 3.初始化
- 4.填表顺序
- 5.返回值
- 1.4.代码讲解
- 1.5.完整代码展示
- 2.删除并获得点数
-
- 2.1.题目来源
- 2.2.题目解析
- 2.3.思路分析
-
- 1.状态表示
- 2.状态转换方程
- 3.初始化
- 4.填表顺序
- 5.返回值
- 2.4.代码讲解
- 2.5.完整代码展示
- 3.总结
1.按摩师
1.1.题目来源
这个题目和之前的题一样来自于力扣，下面小编给出本题的链接：面试题 17.16. 按摩师 - 力扣（LeetCode）
1.2.题目分析
本题也是比较容易读懂的，虽然题干有点长，但是简单的概括下，其实就是一个按摩师在一天可以有两种选择，分别是选择接受预约和不接受预约，如果接受预约的话，那么后一天就不可以在预约了，因为连续两天是不可以去预约的，此时我们需要在一个数列中挑选预约时间，此时我们需要找到预约时间最长的集合，这便是这个题目的大体，下面小编进入题目的思路讲解。
1.3.思路讲解
对于动态规划的题目，我们需要先设置好一个dp表，之后我们就要五步走来分析问题了。
1.状态表示
对于本题的状态表示，我们还是靠经验 + 题目分析来完成这道题目，此时我们根据题意，可以知道此时的dp表有这两种意思，分别是接受预约和接受不预约，此时如果我们光靠一个一维的dp表，那还是远远不够的，所以本题就需要用到两个dp表来解决问题，这便是本节主要讲述的内容——多状态的dp问题，此时我们需要用到两个表，小编分别命名为f和g（高中的f(x) 和 g(x)函数演变而来），当然，虽然分为了两个表，但是我们的分析方法还是一样的，无非就是以i位置为结尾或者开头进行分析问题，此时我们让f[i]代表到达i位置时，接受此预约；g[i]表示达到此位置，不接受此预约；此时我们用了两个表分别表示了此时的状态，下面我们就可以写本题目的状态转换方程。
2.状态转换方程
我们
