首页 > 其他分享 >LC每日一题 198.打家劫舍

LC每日一题 198.打家劫舍

时间:2023-09-16 14:25:10浏览次数:41  
标签:偷窃 LC nums int 金额 房屋 打家劫舍 dp 198

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

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

 

示例 1:

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

 

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

 

这题是一道动态规划的基础题。

假设偷到第n-2家了 剩下第n-1家和第n家没偷 那么自然是从第n家和第n-1家中较大者选 这取决于偷没偷第n-2家。

以此从最后倒推至最前,可得状态转移方程dp[i]=max(dp[i-2]+nums[i],dp[i-1])。

最后return dp[n-1]即可。

AC代码:

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        int dp[n];
        memset(dp,0,sizeof dp);
        if (n==1) return nums[0];
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for (int i=2;i<n;i++){
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[n-1];
    }
};

 

标签:偷窃,LC,nums,int,金额,房屋,打家劫舍,dp,198
From: https://www.cnblogs.com/aomiao/p/17706671.html

相关文章

  • halcon AI读取onnx模型并推理
    *程序功能:读取onnx模型并推理dev_update_off()dev_close_window()read_dl_model('squeezenet.onnx',DLModelHandle)set_dl_model_param(DLModelHandle,'type','classification')get_dl_model_param(DLModelHandle,'image_dimensions',......
  • [ARC122E] Increasing LCMs
    [ARC122E]IncreasingLCMsAtcoder:[ARC122E]IncreasingLCMs洛谷:[ARC122E]IncreasingLCMsSolution应该意识到这题的核心思想在于构造,想办法将原问题不断划分为子问题。此题策略的证明不算太难,但以我目前的水平肯定不可能靠严密的证明做出这道题。猜,直接把满足条件的数放......
  • 6576: 点的距离 倍增LCA
    描述 给定一棵n个点的树,Q个询问,每次询问点x到点y两点之间的距离。 输入 第一行一个正整数n,表示这棵树有n个节点;接下来n−1行,每行两个整数x,y表示x,y之间有一条连边;然后一个整数Q,表示有Q个询问;接下来Q行每行两个整数x,y表示询问x到y的距......
  • 开发环境篇之HALCON数据结构
    开发环境篇之HALCON基础目录基本数据分类图标类数据Image(图片)Pixel:像素Channel:通道Domain:域图片操作Region(区域)Region操作XLD(轮廓)XLD操作Control(控制类数据)数据监视数组Iconic数组(Objects)Control数组(Tuple)Vector数组字典扩展:坐标系和角度参考资料基本数据分类Iconic图......
  • RDLC报表设计与打印相关备忘
    1、RDLC报表设计在最新VSTS集成环境(IDE),如VS2019及以上,不能打开Designer(设计器);VS2015可以(默认已安装)用图形化界面进行设计;2、“报表数据”页签显示:主菜单“视图”->“ReportData”3、设计界面显示标尺,以便直观看到报表的宽度(如下报表宽度27cm+,所以该表设计是横向A4纸张页面布局......
  • 为局域网内已分配固定IP的PLC设备实现NAT转换和跨网段访问
    很多PLC设备在出厂时就已经分配好固定的IP地址。对于工厂来说,需要将这些固定IP的PLC设备接入到工厂局域网中,常常遇见IP冲突、数据采不上来等问题,影响到工厂网络的架构,这时候可以要求厂家修改IP地址,但无法根治。随着新设备的接入,以上问题可能再次出现,通过NAT(网络地址转换)技术可以更......
  • 科技:dfn 求 LCA
    upd:2023.09.13新建非常好思路,学习自Alex_Wei。摘要使用st表维护区间内所有点的dfn最小的父节点。优点是好写、时间空间常数小。前置约定\(dfn_{i}\):\(i\)是第几个被访问的点\(sub_{i}\):以\(i\)为根的子树\(LCA\):\(\text{LCA}(u,v)\)原理dfn的性质:设\(......
  • sqlalchemy 排序方式 flask
    第一种:直接在查询语句中使用order_by现在就用第一种方法实现刚才所说(最新注册的用户的拍在前面),最新注册的也就是时间最大的。代码如下results=session.query(User).order_by(User.create_time.desc()).all()print(results)运行结果如下。 嗯,结果如我们所愿(时间按从大到小......
  • PLC中ST编程的定时器
     PLC中ST编程的定时器TON(IN:=,PT:=,Q=>,ET=>);PT:定时时间,ET:当前累计时间,当IN为TURE,延时到定时时间后,Q为TURE;......
  • 工业数据采集平台可以实现哪些PLC的通信与控制
    在工业化、数字化自动化快速发展的时代,很多企业厂家都很重视数据采集这方面的工作。PLC是工控领域的重要设备,可以控制多种工业设备的自动生产,通过PLC数据采集可以实时了解设备运行状态和工作参数,以便于随时调整生产流程或者及时进行设备维护。对于企业减少设备故障和生产停工有重要......