多状态动态规划之按摩师

这篇具有很好参考价值的文章主要介绍了多状态动态规划之按摩师。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 题目分析

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

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

2. 状态表示

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

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

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

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

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

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

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

3. 状态转移方程

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

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

image.png
这种情况下, 选择了 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
根据状态转移方程, 这时候的最长预约时长就是从起始位置到 i-1 并预约 nums[i-1] 的最长预约时长. 正好对应我们的状态表示, 即为 f[i-1]

  1. 拒绝 nums[i-1]

image.png
根据状态转移方程, 这时候的最长预约时长就是从起始位置到达 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] ) ( 注意下标的对应关系 )文章来源地址https://www.toymoban.com/news/detail-514560.html

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

到了这里,关于多状态动态规划之按摩师的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode刷题详解——按摩师

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

    2024年02月08日
    浏览(41)
  • 动态规划题目练习

    动态规划背包问题-CSDN博客 动态规划基础概念-CSDN博客 题目描述 棋盘上 A 点有一个过河卒,需要走到目标 B 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河

    2024年04月25日
    浏览(37)
  • 【算法】——动态规划题目讲解

    本期继续为大家带来的是关于动态规划类题目的讲解,对于这类题目大家一定要多加练习,争取掌握。 链接如下: 62. 不同路径 题目如下: 算法思路: 1. 状态表⽰:  对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式: i. 从 [i, j] 位置出发; ii. 从起始位置出发

    2024年02月10日
    浏览(42)
  • 动态规划2:题目

    目录 第1题 Fibonacci 第2题 字符串分割(Word Break) .第3题 三角矩阵(Triangle) 第4题 路径总数(Unique Paths) 第5题 最小路径和(Minimum Path Sum) 第6题 背包问题 第7题 回文串分割(Palindrome Partitioning) 第8题 编辑距离(Edit Distance) 第9题 不同子序列(Distinct Subsequences) 分析问题: 1. 状态定义F(i):第

    2024年02月06日
    浏览(43)
  • 【LeetCode】动态规划类题目详解

    所有题目均来自于LeetCode,刷题代码使用的Python3版本 如果某一个问题有重叠的子问题,则使用动态规划进行求解是最有效的。 动态规划中每一个状态一定是由上一个状态推导出来的,这一点区别于贪心算法 动态规划五部曲 确定dp数组以及下标的含义 确定递推公式 dp数组如何

    2024年04月11日
    浏览(49)
  • 代码随想录 动态规划-基础题目

    目录 509.斐波那契数  70.爬楼梯 746.使用最小花费爬楼梯 62.不同路径 63.不同路径|| 343.整数拆分 96.不同的二叉树 509. 斐波那契数 简单 斐波那契数  (通常用  F(n)  表示)形成的序列称为  斐波那契数列  。该数列由  0  和  1  开始,后面的每一项数字都是前面两项数字的和

    2024年03月18日
    浏览(77)
  • 一维动态规划经典力扣题目(一)

    目录 题一:斐波那契数列 题目二:最低票价 题三:解码方法 递归方法是2的n次方的时间复杂度。 递归代码: 带有缓存的递归,会使时间复杂度得到大幅度优化。 时间复杂度为O(n)。 缓存即记录中间值         优化的方法:         代码:         代码:

    2024年02月21日
    浏览(42)
  • C++算法之动态规划(ACWING题目)

    动态规划时间复杂度:状态数量*转移计算量 线性DP 一.数字三角形 动态规划:     1.状态表示:         集合:f[i, j]表示所有从起点走到(i, j)的路径         属性:所有路径上的数字之和的最大值     2.状态计算:         如何得到f[i, j]?             从左边路径走到和

    2024年02月20日
    浏览(42)
  • 【leetcode 力扣刷题】回文串相关题目(KMP、动态规划)

    题目链接:5. 最长回文子串 题目内容: 题目就是要我们找s中的回文子串,还要是最长的。其实想想,暴力求解也行……就是遍历所有的子串,同时判断是不是回文串,是的话再和记录的最大长度maxlen比较,如果更长就更新。时间复杂度直接变成O(n^3)。 优化的点在于,假设子

    2024年02月09日
    浏览(48)
  • 题解动态规划:蓝桥杯2022国赛B组 题解 A题目

    在这组题(蓝桥杯C/C++ B组 国赛)里面挑了几道喜欢的题目,做了一下,笔记思路如下。( 其实是我觉得能做出的题 ) 题目图片来源于:CSDN 罚时大师月色 请问2022,拆分成10个不同的正整数有多少种不同的分法。 这道题目,拿到手上的时候,第一个想法是暴力,但是,每次

    2023年04月08日
    浏览(95)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包