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

文章目录

  • ??前言
  • ??[按摩师](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. 返回值

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

??按摩师

??题目描述

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

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

  • 示例 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]);
    }
}

??打家劫舍二

??题目描述

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

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

  • 示例 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]);
    }
}

??删除并获得点数

??题目描述

给你一个整数数组 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问题——壹》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!