当前位置: 首页 > article >正文

day-81 打家劫舍 II

在这里插入图片描述
思路
与LCR 089. 打家劫舍相比,本题所有房屋围成了一圈,那么第一间房子和最后一间房子不能同时打劫,那么就可以分为两种情况:1.选第一间房打劫;2.选最后一间房打劫

解题过程
然后依次计算出以上两种情况的最大金额(思路LCR 089. 打家劫舍一样),返回较大值即可

Code

class Solution {
    public int rob(int[] nums) {
        int n=nums.length;
        if(n==1) return nums[0];
        if(n==2) return Math.max(nums[0],nums[1]);
        int dp1[]=new int[n];
        dp1[0]=nums[0];
        dp1[1]=nums[0];
        for(int i=2;i<n-1;i++){
            dp1[i]=Math.max(dp1[i-2]+nums[i],dp1[i-1]);
        }
        int dp2[]=new int[n];
        dp2[0]=0;
        dp2[1]=nums[1];
        for(int i=2;i<n;i++){
            dp2[i]=Math.max(dp2[i-2]+nums[i],dp2[i-1]);
        }
        return Math.max(dp1[n-2],dp2[n-1]);
    }
}

作者:菜卷
链接:https://leetcode.cn/problems/house-robber-ii/solutions/2980878/da-jia-jie-she-iichao-yue-100-by-ashi-ji-mmb9/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

http://www.kler.cn/a/383405.html

相关文章:

  • 浏览器工作原理与实践-12|栈空间和堆空间:数据是如何存储的
  • Cesium材质——Material
  • spring专题笔记(六):bean的自动装配(自动化注入)-根据名字进行自动装配、根据类型进行自动装配。代码演示,通俗易懂。
  • docker 搭建集群
  • 网络安全词云图与技术浅谈
  • SOTA简繁中文拼写检查工具:FASPell Chinese Spell Checker 论文
  • Linux篇(文件管理命令)
  • 泷羽sec学习打卡-shodan扫描1
  • 【短视频矩阵系统开发指南与源码构建技术分享】
  • Django命令行操作用户(manage.py工具)
  • Golang--面向对象
  • 智能指针std::shared_ptr
  • 音频怎么转换成二维码?扫码播放音频的制作方法
  • 《XGBoost算法的原理推导》12-7损失函数经验损失项二阶泰勒展开式 公式解析
  • 归并排序:高效算法的深度解析
  • 大模型LLama3!!!Ollama下载、部署和应用(保姆级详细教程)
  • K8s小白入门
  • 【C++笔记】模版的特化及其编译分离
  • 6.qsqlquerymodel源码分析
  • Java Agent使用、用途和优势
  • 第十九周机器学习笔记:GAN的数学理论知识与实际应用的操作
  • URL上的参数获取
  • C++之多态(3)
  • 鸿蒙next打包流程
  • 提升网站流量的有效网页优化方法指南
  • 力扣1 两数之和