多状态动态规划之按摩师

灰太狼 2024-03-16 23:16 75阅读 0赞

## 1. 题目分析 ##

题目链接选自力扣 : [面试题 17.16. 按摩师][17.16.]  
![image.png][]  
还是一样, 根据给的示例 1 来分析看看 :  
![image.png][image.png 1]  
进过分析, 一共有这样几个规定 :

1.  相邻预约不能同时接受
2.  可以从任意一个预约开始
3.  不能之前的
4.  最终总的预约时长要最长的

## 2. 状态表示 ##

以 i 位置为结尾, 表示从某一个位置预约开始到 i 位置结束时的预约最长时间. 用 dp\[i\] 表示.

对于这个题来说, 它还有一点特殊. 你会发现, 当你以上面的状态表示时, 还可以分为其它状态. 什么意思呢 ?  
![image.png][image.png 2]

1.  当达到 i 位置后, 预约了 i 位置

我们把这种情况以 f\[i\] 表示, 即以某一个位置预约开始到 i 位置结束时, nums\[i\] 必选, 此时的最长预约时间

1.  当到达 i 位置后, 不预约 i 位置

我们把这种情况以 g\[i\] 表示, 即以某一个位置月月开始到 i 位置结束时, nums\[i\] 不选, 此时的最长预约时间

**这种多种状态细分状态表示的问题我们称为多状态动态规划. 特点就是状态多可以接着细分 ! 有多个不同状态下的状态转移方程 ! ! !**

## 3. 状态转移方程 ##

同样以最近的一步来划分问题. 由于我们把这个问题更加细分了, 状态转移方程也就和之前的有一点不一样了. 一起来看看

1.  到达 i 位置时, 预约 nums\[i\]

![image.png][image.png 3]  
这种情况下, 选择了 nums\[i\], 相邻的 nums\[i-1\] 就无法预约了. **只需要知道从起始位置到达 i - 1 位置时的最长预约时间加上 nums\[i\] 就是最终预约时间**. 而这对应到我们的状态方程中则为 g\[i-1\].

**最终为这种情况下的最长预约时长为: g\[i-1\] + nums\[i\]**

1.  到达 i 位置时, 不预约 nums\[i\]

当到达 i 位置时, 不预约 nums\[i\], 那么意味着前面一个 nums\[i-1\] 有两种情况

1.  预约 nums\[i-1\]

![image.png][image.png 4]  
根据状态转移方程, 这时候的最长预约时长就是从起始位置到 i-1 并预约 nums\[i-1\] 的最长预约时长. 正好对应我们的状态表示, 即为 f\[i-1\]

1.  拒绝 nums\[i-1\]

![image.png][image.png 5]  
根据状态转移方程, 这时候的最长预约时长就是从起始位置到达 i - 1 位置是的最长预约 时长. 正好对应我们的状态表示, 即为 g\[i-1\]

**最终到达 i 位置时不选择 nums\[i\] 细分的两种情况选择预约时长最长的那种, 最终结果为 : Math.max( f\[i - 1\], g\[i - 1\] )**

这里需要注意的是, **由于我们是多状态的转台表示. 因此最终的结果是需要分开进行处理的.** **也就是最终的状态转移方程有两个**

**f\[i\] = g\[i-1\] + nums\[i\]**  
**g\[i\] = Math.max( f\[i - 1\], g\[i - 1\] )**

## 4. 初始化 ##

在填写 f\[i\] 时根据状态转移方程 f\[i\] = g\[i-1\] + nums\[i\] 和 \*\*Math.max( f\[i - 1\], g\[i - 1\] ) \*\*会存在越界情况. 因此我们需要初始化 g\[0\] 和 f\[0\].

经过分析, 当只有一个元素时. 最长的预约时长就是 nums\[0\] 它是必选的, 对应到我们的状态表示则为 f\[0\] = nums\[0\].  
同样, 当只有一个元素时, 可以选择拒绝不预约, 此时的最长预约时间就是 0. 对应到我们的状态表示则为 g\[0\] = 0

## 5. 填表顺序 ##

填表顺序还是很清晰的, 一个线性的表, 从左往右填写即可.

## 6. 返回值 ##

根据题目要求, 返回到达**指定数组的末尾位置时最长的预约时间**. 而我们的转态表示有两种情况. 一种到达结尾时预约该点. 一种不预约最终都有一个最长预约时间. 而我们要的是两种情况的最长预约时间. 因此返回值为 Math.max( f\[n-1\], g\[i-1\] ) ( 注意下标的对应关系 )

## 7. 代码演示 ##

class Solution {
        
        public int massage(int[] nums) {
        
    
            // 1. 创建 dp 表
            // 有两个状态表示, 需要两个 dp 表
            int n = nums.length;
            int[] f = new int[n]; // 表示预约 nums[i]
            int[] g = new int[n]; // 表示不预约 nums[i]
    
            // 特殊情况处理, 防止 f[0] 初始化越界
            if(n == 0) {
        
                return 0;
            }
            
            // 2. 初始化
            f[0] = nums[0];
            g[0] = 0;
    
            // 3. 填写 dp 表
            for(int i = 1; i < n; i++) {
        
                // 根据状态转移方程填写
                f[i] = g[i - 1] + nums[i];
                g[i] = Math.max(f[i - 1], g[i -1]); 
            }
    
            // 4. 确认返回值
            return Math.max(f[n - 1], g[n - 1]);
        }
    }

[17.16.]: https://leetcode.cn/problems/the-masseuse-lcci/
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2ed7baeca872462a98fbc716d3a973f3.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/cfc137bbf9d14803addc15761a347977.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c8e0d5cd75ca44179007030a20dce48c.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c5c838c871dc4afca2b228c7e0276984.png
[image.png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/23684899ae9b4c74a1b25bebf0e84202.png
[image.png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f9757977f287489c9c80c7c1d3a416b3.png