【LeetCode】动态规划 刷题训练(四)

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

面试题 17.16. 按摩师(打家劫舍|)

点击查看:按摩师


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

示例 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。


题目解析

【LeetCode】动态规划 刷题训练(四)

从第一个数1开始,相邻的数不能够放在一起,所以再次 选择 3
即 1+3 =4
从第二个数2开始,相邻的数不能够放在一起,所以再次 选择 1
即 2+1 =3
所以 4 作为最长预约时长

状态转移方程

在上述分析过程中发现,是从左往右的

dp[i] :表示 选到i位置的时候,此时的最长预约时长


对于i位置有两种情况:

1. 选择i 位置的值,选择用f 表示
f[i]:表示 选择i位置的时候,i位置的值(nums[i]) 必选,此时的最长预约时长

2. 不选 i位置的值,不选用g表示
g[i]:表示 选择i位置的时候,i位置的值(nums[i]) 不选, 此时的最长预约时长


【LeetCode】动态规划 刷题训练(四)

f[i]表示 i位置必定选择,则i-1位置必定不能被选
因为要的是最长预约时长,所以寻找[0,i-1] 区间内的最长预约时长 ,而i-1位置不能够被取到 即g[i-1]
再加上i位置的值 为 [0,i]区间的最长预约时长

状态转移方程 为:
f[i] = g[i-1]+nums[i]


【LeetCode】动态规划 刷题训练(四)

g[i] 表示 i位置必定不选,则i-1位置分为两种情况
第一种情况,i-1位置被选择
因为要的是最长预约时长,所以寻找[0,i-1] 区间内的最长预约时长 ,而i-1位置能够被取到 即f[i-1]
第一种情况下的最长预约时长为 : g[i]=f[i-1]

第二种情况,i-1位置不选
因为要的是最长预约时长,所以寻找[0,i-1] 区间内的最长预约时长 ,而i-1位置不能够被取到 即g[i-1]
第二种情况下的最长预约时长为 : g[i]=g[i-1]

状态转移方程为:
g[i] =max(f[i-1],g[i-1]);


完整代码

class Solution {
public:
    int massage(vector<int>& nums) {
       int n=nums.size();

       //处理边界条件
       if(n==0)
       {
           return 0;
       }
       vector<int>f(n,0);
       vector<int>g(n,0);
       int i=0;

       //为了防止越界问题 g[0]和f[0]都需要提前赋值
       g[0]=0;
       f[0]=nums[0];
       for(i=1;i<n;i++)
       {
          f[i]=g[i-1]+nums[i];
          g[i]=max(f[i-1],g[i-1]);
       }
       //返回 取到最后一个位置和 不取最后一个位置 两者的最大值
       return max(f[n-1],g[n-1]);
    }
};

i从1开始,所以要初始化f[0]和g[0]
f[0]包含nums[0]位置的值,所以为nums第一个元素
g[0]不包含nums[0]位置的值,所以为0

返回值为 到最后一个位置选 和到最后一个位置不选,两者中的最大值

213. 打家劫舍 II

点击查看:打家劫舍 II


你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金

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

题目解析

相当于 打家劫舍| 不同点在于 首尾是相连的

【LeetCode】动态规划 刷题训练(四)

若取第一个节点中的值 2 ,则不能取第三个节点中的值 2 ,因为收尾相连 ,所以此时 能够偷取的金额为2

若 取 第二个节点中的值 3 ,则能够偷取的金额为3
所以 最大偷取金额 为 3

通过分类讨论,将环形问题,转换为两个线性的打家劫舍|


情况一:

【LeetCode】动态规划 刷题训练(四)

若偷取下标为0 的位置,因为首尾相连,所以下标为1的 位置 和 下标为n-1的位置就不能偷取到了
而在[2,n-2]区间内 随便偷取(用动态转移方程)


情况二:

【LeetCode】动态规划 刷题训练(四)

若 不偷取 下标为0的位置,此时[1,n-1]区间内可以随便偷取(用动态转移方程)

取 两种情况下的最大值 即为 最大金额

状态转移方程

该动态转移方程 是用于上述分析的情况1中[2,n-2]区间内 随便偷取 和情况2中[1,n-1]区间内可以随便偷取的 情况


f[i]:表示偷取到i位置时,偷nums[i],此时的最大金额
g[i]:表示偷取到i位置时,不偷nums[i],此时的最大金额


【LeetCode】动态规划 刷题训练(四)

若i位置被偷取到 nums[i]的值,则想要求[0,i]的最大金额,就要先求[0,i-1]的最大金额
而由于相邻位置不能偷取,所以i-1位置不能偷取,即g[i-1]
再加上nums[i]的值 为为 [0,i]区间的最大金额

状态转移方程 为:
f[i]=g[i-1]+nums[i]


【LeetCode】动态规划 刷题训练(四)

若i位置没有被偷取到 nums[i]的值,则i-1位置分为两种情况:

情况一:
若i-1位置的值被偷取,
因为要的是最大金额,所以寻找[0,i-1] 区间内的最长金额 ,而i-1位置能够被取到 即f[i-1]
第一种情况下的最大金额为 : g[i]=f[i-1]

情况二:
若i-1位置的值没有被偷取,
因为要的是最大金额,所以寻找[0,i-1] 区间内的最大金额 ,而i-1位置不能够被取到 即g[i-1]
第二种情况下的最长最大金额为 : g[i]=g[i-1]

状态转移方程 为:
g[i]=max(f[i-1],g[i-1]);

完整代码

class Solution {
public:
    int rob1(vector<int> &nums,int left,int right)
    {
        //区间不存在
        if(left>right)
        {
            return 0;
        }
        int n=nums.size();
        vector<int>f(n,0);
        vector<int>g(n,0);
        int i=0;
        //为了防止越界问题,所以下标left处要提前赋值
        f[left]=nums[left];
        g[left]=0;
        for(i=left;i<=right;i++)
        {
            f[i]=g[i-1]+nums[i];
            g[i]=max(f[i-1],g[i-1]);
        }
        //求 取到最后一个位置 和 没有取到最后一个位置 两者的最大值
        return max(f[right],g[right]);
    }
    int rob(vector<int>& nums) {
        int n=nums.size();
        //第一个位置取到值 和 第一个位置没有取到值 的两种情况
       return max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1));
    }
};

n的取值为1到100,若n为1时,n-2为-1,就会导致下标left(1) 小于下标right(2) ,区间不存在

调用rob1,就在区间[left,right]内随便偷取,就相当于打家劫舍|的代码在调用

740. 删除并获得点数

点击查看:删除并获得点数


给你一个整数数组 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 个点数。

题目解析

【LeetCode】动态规划 刷题训练(四)
删除一个3,并获取3个点数,同时所有的2和4也被删除,依次删除3,并获取对应的点数
共获取 9个点数

预处理

【LeetCode】动态规划 刷题训练(四)

若储存的数都是连续的,则相当于打家劫舍问题(不能选择两个相邻的数)
如:若选取 1 ,则不能选取2


【LeetCode】动态规划 刷题训练(四)

但是像这种不连续的数 ,缺少数字3和5 6,就没办法使用 类似打家劫舍问题的解决方法


【LeetCode】动态规划 刷题训练(四)

借助下标表示 对应的数,如:下标为1,表示为1的数
arr[i] :表示 i 这个数,出现的总和
此时的下标就是连续的,就可以借助 打家劫舍问题的解决方法
如:若选取下标为1的数,则就不能选取下标为2的数,只能选择下标为3的数或者 下标为4的数

将原数组中数统计到 arr数组中,在arr数组中进行 打家劫舍

状态转移方程

以下就是 打家劫舍问题的状态转移方程(就是把原数组变为了arr数组,其他都是一样的)


对于i位置有两种情况:
1. 选择i 位置的值,选择用f 表示
f[i]:表示 选择i位置的时候,i位置的值(arr[i]) 必选,此时的最大点数

2. 不选 i位置的值,不选用g表示
g[i]:表示 选择i位置的时候,i位置的值(arr[i]) 不选, 此时的最大点数


【LeetCode】动态规划 刷题训练(四)

f[i]表示 i位置必定选择,则i-1位置必定不能被选
因为要的是最大点数,所以寻找[0,i-1] 区间内的最大点数 ,而i-1位置不能够被取到 即g[i-1]
再加上i位置的值 为 [0,i]区间的最大点数

状态转移方程 为:
f[i] = g[i-1]+arr[i]


【LeetCode】动态规划 刷题训练(四)

g[i] 表示 i位置必定不选,则i-1位置分为两种情况
第一种情况,i-1位置被选择
因为要的是最大点数,所以寻找[0,i-1] 区间内的最大点数 ,而i-1位置能够被取到 即f[i-1]
第一种情况下的最大点数为 : g[i]=f[i-1]

第二种情况,i-1位置不选
因为要的是最大点数,所以寻找[0,i-1] 区间内的最大点数 ,而i-1位置不能够被取到 即g[i-1]
第二种情况下的最大点数为 : g[i]=g[i-1]

状态转移方程为:
g[i] =max(f[i-1],g[i-1]);
文章来源地址https://www.toymoban.com/news/detail-500978.html

完整代码

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
         int i=0;
         int maxsize=0;
         //因为arr数组下标最大值为原数组的最大值 所以寻找原数组的最大值
         for(i=0;i<nums.size();i++)
         {
            if(nums[i]>maxsize)
            {
                maxsize=nums[i];
            }
         }
         //通过原数组的最大值创建arr数组大小
         vector<int>arr(maxsize+1,0);
         for(i=0;i<nums.size();i++)
         {
             //arr[i]代表 i这个数的总和
             arr[nums[i]]+=nums[i];
         }
         //下面进行 打家劫舍问题
        int n=arr.size();
        //[i]f代表取arr[i]这个位置的时候,能够得到的最大点数
        //g[i]代表不能取arr[i]这个位置的时候,能够得到的最大点数
         vector<int>g(n,0);
         vector<int>f(n,0);
         //为了避免越界 将g[0] f[0]进行初始化
         g[0]=0;
         f[0]=arr[0];
         for(i=1;i<n;i++)
         {
             //状态转移方程
             f[i]=g[i-1]+arr[i];
             g[i]=max(g[i-1],f[i-1]);
         }
         //返回 取到最后一个位置 和 不取最后一个位置 两者中的最大值
         return max(f[n-1],g[n-1]);
    }
};

到了这里,关于【LeetCode】动态规划 刷题训练(四)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【LeetCode】动态规划 刷题训练(二)

    点击查看:不同路径 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示例 1: 输入:m = 3, n = 7 输出:28 示例

    2024年02月10日
    浏览(33)
  • 【LeetCode】动态规划 刷题训练(五)

    点击查看:粉刷房子 假如有一排房子,共 n 个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。 当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。

    2024年02月11日
    浏览(44)
  • 【LeetCode】动态规划 刷题训练(九)

    点击查看:467. 环绕字符串中唯一的子字符串 定义字符串 base 为一个 “abcdefghijklmnopqrstuvwxyz” 无限环绕的字符串,所以 base 看起来是这样的: “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”. 给你一个字符串 s ,请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

    2024年02月15日
    浏览(36)
  • 17.16按摩师

    目录 一、题目 二、分析+代码 面试题 17.16. 按摩师 - 力扣(LeetCode)    

    2024年02月08日
    浏览(53)
  • 力扣 -- 面试题 17.16. 按摩师

    题目链接:面试题 17.16. 按摩师 - 力扣(LeetCode)  下面是用动态规划的思想解决这道题的过程,相信各位小伙伴都能看懂并且掌握这道经典的动规题目滴。 参考代码:  以上就是分析这道dp题目的整个过程啦,你学会了吗?如果以上题解对你有所帮助,那么就点亮一下小心心

    2024年02月12日
    浏览(39)
  • Leetcode刷题详解——按摩师

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

    2024年02月08日
    浏览(41)
  • 多状态动态规划之按摩师

    题目链接选自力扣 : 面试题 17.16. 按摩师 还是一样, 根据给的示例 1 来分析看看 : 进过分析, 一共有这样几个规定 : 相邻预约不能同时接受 可以从任意一个预约开始 不能之前的 最终总的预约时长要最长的 以 i 位置为结尾, 表示从某一个位置预约开始到 i 位置结束时的预约最长

    2024年02月11日
    浏览(32)
  • 算法刷题打卡049 | 动态规划17

    动态规划终于要刷完了!虽然动规五部曲已经烂熟,也刷了有二三十题经典的动态规划题,但是自己实际做题时未必能用的很好,一方面是有些题目实在很难想到用动规解题,另一方面是即使想到动态规划,往往卡在状态的定义和状态转移上(更别说一些细节了,比如初始化

    2023年04月15日
    浏览(37)
  • 《动态规划》刷题训练

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动

    2024年01月19日
    浏览(45)
  • Leetcode 刷题 动态规划

    309. 最佳买卖股票时机含冷冻期 1. 确定dp数组以及下标的含义 具体可以区分出如下四个状态: 状态一:持有股票状态(今天买入股票,或者是之前就买入了股票然后没有操作,一直持有) 不持有股票状态,这里就有两种卖出股票状态 状态二:保持卖出股票的状态(两天前就

    2024年02月11日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包