动态规划多状态问题解析
概述
在动态规划的众多问题中，多状态 DP 问题是一个非常重要的类别。它的难点在于如何设计合适的状态表示和转移方程，从而高效地解决问题。
多状态 DP 的核心思想在于：针对问题的不同属性或限制条件，将状态表示扩展为多个维度，使得状态可以更加精确地描述问题的子结构。这种方法既可以帮助我们更好地分解问题，又能够在求解过程中保留更多的信息，从而为最终的结果提供完整的支持。
在实际应用中，多状态 DP 常用于解决路径规划、背包问题、字符串编辑、博弈问题等场景。例如，在路径规划问题中，我们可以通过增加状态的维度来描述位置、步数以及路径的某些限制条件；在资源分配问题中，我们可以通过扩展状态来考虑当前的资源利用率和历史决策。
本篇内容将聚焦于多状态 DP 问题的基本原理和解决方法，结合典型实例，逐步介绍从状态定义、转移方程设计到代码实现的完整过程。
1. 按摩师
1.1 题目来源
本题来源于力扣面试题：面试题 17.16. 按摩师。
1.2 题目分析
本题题干概括如下：一个按摩师在一天可以有两种选择，分别是选择接受预约和不接受预约。如果接受预约的话，那么后一天就不可以再预约了，因为连续两天是不可以去预约的。此时我们需要在一个数列中挑选预约时间，找到预约时间最长的集合。
1.3 思路讲解
对于动态规划的题目，我们需要先设置好一个 dp 表，之后通过五步法来分析问题。
1. 状态表示
对于本题的状态表示，根据题意，dp 表有两种含义，分别是接受预约和接受不预约。光靠一个一维的 dp 表远远不够，本题需要用到两个 dp 表来解决问题，即多状态的 DP 问题。分别命名为 f 和 g：
- f[i] 代表到达 i 位置时，接受此预约。
- g[i] 表示达到此位置，不接受此预约。
2. 状态转换方程
首先求 f 表的状态转换方程。已知 f 表代表了 i 位置已经接受了预约，此时可以判定 i-1 位置肯定是不预约的（相邻两个位置不能预约），因此：
f[i] = g[i - 1] + nums[i];
接着判断 g[i]。相比于 f[i]，g[i] 稍微复杂一些。i-1 分为两种情况，分别是前一天预约了和前一天没预约。因为此时 i 位置代表着不预约，无法说明它的前一天到底是预约了还是没有预约，所以需要判断这两个谁最大，使用 max 函数表示出此时的方程：
g[i] = max(f[i - 1], g[i - 1]);
3. 初始化
需要根据具体边界条件进行初始化，通常处理数组长度为 0 或 1 的情况。
4. 填表顺序
按照索引从小到大的顺序依次计算。
5. 返回值
最终结果为 max(f[n-1], g[n-1])，其中 n 为输入数组长度。
