LCR 090. 打家劫舍 II(leetcode)动态规划

2023-12-10 02:30

本文主要是介绍LCR 090. 打家劫舍 II(leetcode)动态规划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
  • 一、题目分析
  • 二、算法原理
    • 1.状态表示
    • 2.状态转移方程
    • 3.初始化
    • 4.填表顺序
    • 5.返回值是什么
  • 三、代码实现
  • 总结


前言

在本文章中,我们将要详细介绍一下LeetcodeLCR 090. 打家劫舍 II。采用动态规划解决,这是一道经典的多状态dp问题

一、题目分析

在这里插入图片描述
计算小偷能偷到的最大金额数,并且题目规定:
  🥉.两个相邻的房屋不能被偷
  🥉.第一个房屋和最后一个房屋不能被偷
规定1比较好解决,对于规定2,我们采用分情况讨论的方法解决
  🍔.第一个房间偷,第二个房间和最后一个不被偷,在(2,n-2)下标之间寻找最大金额,再加上nums[0].
  🍔.第一个房间不被偷,最后一个房间不确定,在(1,n-1)下标之间寻找最大金额
  🍔.二者取最大值,就是题目所返回的值

二、算法原理

1.状态表示

列出dp表,dp表中值的含义是什么
这可以细分为两个表,因为经过该房间时不确定偷与不偷
  ⭐️ .f[i]表示到达i房间时,资金被偷
  ⭐️.g[i]表示到达i房间时,资金没有被偷

2.状态转移方程

根据最近一步划分问题
  🌟 f[i]:i位置被偷,那么根据题目规定,i-1位置就不能被偷,这不就正好是g[i-1],再加上i位置被偷的资金;
  🌟g[i]:i位置没有被偷,i-1位置我们不确定有没有被偷,所以需要分为两种情况,这两种情况取最大值
    🐧.i-1位置也没有被偷,就是g[i-1]
    🐧.i-1位置被偷了,就是f[i-1]
结论:
  f[i]=g[i-1]+nums[i];
  g[i]=max(g[i-1],f[i-1])

3.初始化

保证填表不越界
  f[1]需要g[0]的值;g[1]需要g[0]和f[0]的值, 所以需要初始化g[0]和f[0].
  不用开辟额外的空间,这道题目的初始化很简单。
注意:数组的下标和边界条件

4.填表顺序

两个表一起填,从左往右

5.返回值是什么

max(f[n-1],g[n-1]);

三、代码实现

class Solution {
public:int massage(vector<int>& nums,int left,int right) {if(left>right){return 0;}//建表int n=nums.size();int f[n];int g[n];//初始化for(int i=0;i<n;i++){f[i]=g[i]=0;}f[left]=nums[left];g[0]=0;//填表for(int i=left;i<=right;i++){f[i]=g[i-1]+nums[i];g[i]=max(g[i-1],f[i-1]);}//返回值return max(f[right],g[right]);}int rob(vector<int>& nums) {int  n=nums.size();//下标int ret1=massage(nums,2,n-2)+nums[0];int ret2=massage(nums,1,n-1);return max(ret1,ret2);}
};

总结

以上就是我们对LeetcodeLCR 090. 打家劫舍 II(leetcode)详细介绍,希望对大家的学习有所帮助,仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~

这篇关于LCR 090. 打家劫舍 II(leetcode)动态规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/475770

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &