解锁动态规划的奥秘：从零到夺目的创新头脑分析（6）

解锁动态规划的奥秘：从零到夺目的创新头脑分析（6）

媒介：
在动态规划的浩繁题目中，多状态DP题目是一个非常告急的种别。它的难点在于怎样筹划符合的状态表现和转移方程，从而高效地办理题目。
多状态DP的焦点头脑在于：针对题目的差异属性或限定条件，将状态表现扩展为多个维度，使得状态可以更加精确地形貌题目的子结构。这种方法既可以资助我们更好地分解题目，又可以大概在求解过程中生存更多的信息，从而为终极的结果提供完备的支持。
在实际应用中，多状态DP常用于办理路径规划、背包题目、字符串编辑、博弈题目等场景。比方，在路径规划题目中，我们可以通过增长状态的维度来形貌位置、步数以及路径的某些限定条件；在资源分配题目中，我们可以通过扩展状态来思量当前的资源使用率和汗青决议。
本篇内容将聚焦于多状态DP题目的根本原理和办理方法，团结典范实例，渐渐先容从状态界说、转移方程筹划到代码实现的完备过程。盼望通过这一系列解说，读者可以大概对多状态DP的理论和实践有更深入的明白，把握其在办理实际题目时的本领与方法。
本日小编就要开启动态规划的多状态dp题目的解说了，盼望我讲完几篇文章后，对屏幕后的你会有肯定水平的资助，那么废话不多说，开启本日的做题之旅。

  
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位置时，继承此预约；g表现到达此位置，不继承此预约；此时我们用了两个表分别表现了此时的状态，下面我们就可以写本标题的状态转换方程。
2.状态转换方程

我们可以先求f表的状态转换方程，此时我们知道了此时f表代表了什么，以是此时我们知道此时的i位置已经继承了预约，此时我们就可以判定i-1位置肯定是不会预约的（相邻两个位置不能预约），以是此时我们就可以表现出f。

1. f[i] = g[i - 1] + nums[i];

复制代码

之后我们在判定此时的g，相比于f，g就复杂了一丢丢，此时我们可以把i-1分为两种环境，分别是前一天预约了和前一天没预约，由于此时i位置代表着不预约，这就不好分析它的前一天到底是预约了还是没有预约，以是此时我们须要判定一下选手，判定的条件也是很简单，此时我们仅需判定这两个谁最大就可以了，以是此时我们用max函数便可以表现出此时的方程。

1. g[i] = max(f[i - 1],g[i - 1]);

复制代码

<