【算法优选】动态规划之简单多状态dp问题——壹

你的名字 2024-04-17 10:46 33阅读 0赞

#### 文章目录 ####

*  ?前言
 *  ?\[按摩师\](https://leetcode.cn/problems/the-masseuse-lcci/)
 *   *  ?题目描述
     *  ?算法思路：
     *  ?代码实现
 *  ?\[打家劫舍二\](https://leetcode.cn/problems/house-robber-ii/description/)
 *   *  ?题目描述
     *  ?算法思路：
     *  ?代码实现
 *  ?\[删除并获得点数\](https://leetcode.cn/problems/delete-and-earn/description/)
 *   *  ?题目描述
     *  ?算法思路
     *  ?代码实现
 *  ⭕总结

## ?前言 ##

动态规划相关题目都可以参考以下五个步骤进行解答：

1.  状态表⽰
2.  状态转移⽅程
3.  初始化
4.  填表顺序
5.  返回值

后面题的解答思路也将按照这五个步骤进行讲解。

## ?[按摩师][Link 1] ##

### ?题目描述 ###

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

注意：本题相对原题稍作改动

*  示例 1：  
    输入： \[1,2,3,1\]  
    输出： 4  
    解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
 *  示例 2：  
    输入： \[2,7,9,3,1\]  
    输出： 12  
    解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
 *  示例 3：  
    输入： \[2,1,4,5,3,1,1,3\]  
    输出： 12  
    解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

class Solution {
        
        public int massage(int[] nums) {
        
    
        }
    }

### ?算法思路： ###

1.  状态表⽰：

对于简单的线性 dp ，我们可以⽤「经验+题⽬要求」来定义状态表⽰：

*  以某个位置为结尾；
 *  以某个位置为起点。

这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰：  
dp\[i\] 表⽰：选择到 i 位置时，此时的最⻓预约时⻓。

但是我们这个题在 i 位置的时候，会⾯临「选择」或者「不选择」两种抉择，所依赖的状态需要细分：

*  f\[i\] 表⽰：选择到 i 位置时， nums\[i\] 必选，此时的最⻓预约时⻓；
 *  g\[i\] 表⽰：选择到 i 位置时， nums\[i\] 不选，此时的最⻓预约时⻓。

1.  状态转移⽅程：

因为状态表⽰定义了两个，因此我们的状态转移⽅程也要分析两个：  
对于 f\[i\] ：

*  如果 nums\[i\] 必选，那么我们仅需知道 i - 1 位置在不选的情况下的最⻓预约时⻓，然后加上 nums\[i\] 即可，因此 f\[i\] = g\[i - 1\] + nums\[i\] 。

对于 g\[i\] ：

*  如果 nums\[i\] 不选，那么 i - 1 位置上选或者不选都可以。因此，我们需要知道 i- 1 位置上选或者不选两种情况下的最⻓时⻓，因此g\[i\] = max(f\[i - 1\], g\[i- 1\]) 。

1.  初始化：  
    这道题的初始化⽐较简单，因此⽆需加辅助节点，仅需初始化 f\[0\] = nums\[0\], g\[0\] = 0 即可。
2.  填表顺序  
    根据「状态转移⽅程」得「从左往右，两个表⼀起填」。
3.  返回值  
    根据「状态表⽰」，应该返回 max(f\[n - 1\], g\[n - 1\]) 。

### ?代码实现 ###

class Solution
    {
        
    	public int massage(int[] nums)
    	{
        
    		// 1. 创建 dp 表
    		// 2. 初始化
    		// 3. 填表
    		// 4. 返回值
    		int n = nums.length;
    		if(n == 0) return 0; // 处理边界条件
    		int[] f = new int[n];
    		int[] g = new int[n];
    		f[0] = nums[0];
    		for(int i = 1; i < n; i++)
    		{
        
    			f[i] = g[i - 1] + nums[i];
    			g[i] = Math.max(f[i - 1], g[i - 1]);
    		}
    		return Math.max(g[n - 1], f[n - 1]);
    	}
    }

当然博主这里还提供另一种解题方法，就不讲解了，直接给出代码，代码如下：

class Solution {
        
        public int massage(int[] nums) {
        
            int len = nums.length;
            if(len == 0) {
        
                return 0;
            }
            if(len == 1) {
        
                return nums[0];
            }
           int[] dp = new int[len + 1];
            dp[1] = nums[0];
            dp[2] = nums[1];
            for(int i = 3; i <= len ; i++) {
        
                int max = Math.max(dp[i-2],dp[i-3]);
                dp[i] = nums[i-1] + max;
    
            }
            return  Math.max(dp[len-1],dp[len]);
        }
    }

## ?[打家劫舍二][Link 2] ##

### ?题目描述 ###

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

*  示例 1：  
    输入：nums = \[2,3,2\]  
    输出：3  
    解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
 *  示例 2：  
    输入：nums = \[1,2,3,1\]  
    输出：4  
    解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。
 *  示例 3：  
    输入：nums = \[1,2,3\]  
    输出：3

### ?算法思路： ###

这⼀个问题是「打家劫舍I」问题的变形。

上⼀个问题是⼀个「单排」的模式，这⼀个问题是⼀个「环形」的模式，也就是⾸尾是相连的。但是我们可以将「环形」问题转化为「两个单排」问题：

*  偷第⼀个房屋时的最⼤⾦额x ，此时不能偷最后⼀个房⼦，因此就是偷 \[0, n - 2\] 区间的房⼦；
 *  不偷第⼀个房屋时的最⼤⾦额 y ，此时可以偷最后⼀个房⼦，因此就是偷 \[1, n - 1\] 区间的房⼦；

两种情况下的「最⼤值」，就是最终的结果。

因此，问题就转化成求「两次单排结果的最⼤值」。

### ?代码实现 ###

class Solution
    {
        
        public int rob(int[] nums) {
        
            int n = nums.length;
            return Math.max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
        }
        public int rob1(int[] nums, int left, int right) {
        
            if(left > right) return 0;
            // 1. 创建 dp 表
            // 2. 初始化
            // 3. 填表
            // 4. 返回
            int n = nums.length;
            int[] f= new int[n];
            int[] g= new int[n];
            f[left] = nums[left];
            for(int i = left + 1; i <= right; i++)
            {
        
                f[i] = g[i - 1] + nums[i];
                g[i] = Math.max(g[i - 1], f[i - 1]);
            }
            return Math.max(f[right], g[right]);
        }
    }

## ?[删除并获得点数][Link 3] ##

### ?题目描述 ###

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums\[i\] ，删除它并获得 nums\[i\] 的点数。之后，你必须删除 所有 等于 nums\[i\] - 1 和 nums\[i\] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

*  示例 1：  
    输入：nums = \[3,4,2\]  
    输出：6  
    解释：  
    删除 4 获得 4 个点数，因此 3 也被删除。之后，删除 2 获得 2 个点数。总共获得 6 个点数。
 *  示例 2：  
    输入：nums = \[2,2,3,3,3,4\]  
    输出：9  
    解释：  
    删除 3 获得 3 个点数，接着要删除两个 2 和 4 。之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。总共获得 9 个点数。

class Solution {
        
        public int deleteAndEarn(int[] nums) {
        
    
        }
    }

### ?算法思路 ###

其实这道题依旧是「打家劫舍I」问题的变型。

我们注意到题⽬描述，选择 x 数字的时候， x - 1 与 x + 1 是不能被选择的。像不像「打家劫舍」问题中，选择 i 位置的⾦额之后，就不能选择 i - 1 位置以及 i + 1 位置的⾦额呢~

因此，我们可以创建⼀个⼤⼩为 10001 （根据题⽬的数据范围）的 hash 数组，将nums 数  
组中每⼀个元素 x ，累加到 hash 数组下标 x 的位置处，然后在 hash 数组上来⼀次「打家劫舍」即可

### ?代码实现 ###

class Solution {
        
        public int deleteAndEarn(int[] nums) {
        
            int[] arr = new int[10001];
            for(int i = 0; i < nums.length; i++) {
        
                arr[nums[i]] += nums[i];
            }
            int[] f= new int[10001];
            int[] g= new int[10001];
            f[0] = arr[0];
            for(int i = 1; i < 10001; i++)
            {
        
                f[i] = g[i - 1] + arr[i];
                g[i] = Math.max(g[i - 1], f[i - 1]);
            }
            return Math.max(f[10000], g[10000]);
        }
    }

## ⭕总结 ##

关于《【算法优选】 动态规划之简单多状态dp问题——壹》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！

[Link 1]: https://leetcode.cn/problems/the-masseuse-lcci/
[Link 2]: https://leetcode.cn/problems/house-robber-ii/description/
[Link 3]: https://leetcode.cn/problems/delete-and-earn/description/