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

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


🎋前言

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

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

相关文章
|
1月前
|
机器学习/深度学习 存储 算法
动态规划算法深度解析:0-1背包问题
0-1背包问题是经典的组合优化问题,目标是在给定物品重量和价值及背包容量限制下,选取物品使得总价值最大化且每个物品仅能被选一次。该问题通常采用动态规划方法解决,通过构建二维状态表dp[i][j]记录前i个物品在容量j时的最大价值,利用状态转移方程避免重复计算子问题,从而高效求解最优解。
276 1
|
8月前
|
存储 算法 Java
算法系列之动态规划
动态规划(Dynamic Programming,简称DP)是一种用于解决复杂问题的算法设计技术。它通过将问题分解为更小的子问题,并存储这些子问题的解来避免重复计算,从而提高算法的效率。
290 4
算法系列之动态规划
|
9月前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
234 5
|
8月前
|
算法 安全 调度
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
|
8月前
|
机器学习/深度学习 算法 测试技术
【动态规划篇】01 背包的逆袭:如何用算法装满你的 “财富背包”
【动态规划篇】01 背包的逆袭:如何用算法装满你的 “财富背包”
|
22天前
|
传感器 机器学习/深度学习 编解码
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
137 3
|
27天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
16天前
|
机器学习/深度学习 算法 数据可视化
基于MVO多元宇宙优化的DBSCAN聚类算法matlab仿真
本程序基于MATLAB实现MVO优化的DBSCAN聚类算法,通过多元宇宙优化自动搜索最优参数Eps与MinPts,提升聚类精度。对比传统DBSCAN,MVO-DBSCAN有效克服参数依赖问题,适应复杂数据分布,增强鲁棒性,适用于非均匀密度数据集的高效聚类分析。
|
16天前
|
开发框架 算法 .NET
基于ADMM无穷范数检测算法的MIMO通信系统信号检测MATLAB仿真,对比ML,MMSE,ZF以及LAMA
简介:本文介绍基于ADMM的MIMO信号检测算法,结合无穷范数优化与交替方向乘子法,降低计算复杂度并提升检测性能。涵盖MATLAB 2024b实现效果图、核心代码及详细注释,并对比ML、MMSE、ZF、OCD_MMSE与LAMA等算法。重点分析LAMA基于消息传递的低复杂度优势,适用于大规模MIMO系统,为通信系统检测提供理论支持与实践方案。(238字)
|
27天前
|
机器学习/深度学习 传感器 算法
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
147 14

热门文章

最新文章