198. 打家劫舍

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

原题链接:

198. 打家劫舍

https://leetcode.cn/problems/house-robber/description/

完成情况:

198. 打家劫舍,java学习,算法知识,# LeetCode题解,算法,leetcode,数据结构,回归,排序算法文章来源地址https://www.toymoban.com/news/detail-807248.html

参考代码:

_198打家劫舍

package 代码随想录.动态规划;

public class _198打家劫舍 {
    /**
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        // TODO 每次偷窃后,必须至少冷却一天,问多大头去数量数多少
        if(nums == null || nums.length == 0){
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        //有多个时,才需要使用到dp
        int [] dp = new int[nums.length];
        //模拟出取每一个长度位置时的最大累计和
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0],nums[1]);
        for (int i=2;i< nums.length;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.length - 1];
    }
}

_198打家劫舍_滚动优化

package 代码随想录.动态规划;

public class _198打家劫舍_滚动优化 {
    /**
     * 进一步对滚动数组的空间优化 dp数组只存与计算相关的两次数据
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        //初始化dp数组
        //优化空间,dp数组只用2个空间,只记录与当前计算相关的前两个结果
        int [] dp = new int[2];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        int res = 0;
        //遍历
        for (int i=2;i< nums.length;i++){
            res = Math.max((dp[0] + nums[i]),dp[1]);
            dp[0] = dp[1];
            dp[1] = res;
        }
        //输出结果
        return dp[1];
    }
}

_198打家劫舍_滚动数组

package 代码随想录.动态规划;

public class _198打家劫舍_滚动数组 {
    /**
     * 分析本题可以发现,所求结果仅依赖于前两种状态,此时可以使用滚动数组思想将空间复杂度降低为3个空间
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0){
            return 0;
        } else if (len == 1) {
            return nums[0];
        }else if (len == 2){
            return Math.max(nums[0],nums[1]);
        }
        //如果存在多个时。每次只看目之所及的三个
        int result [] = new int[3]; //用来存放选择的结果
        result[0] = nums[0];
        result[1] = Math.max(nums[0],nums[1]);
        //迭代遍历完整个数组
        for (int i=2;i< len;i++){
            result[2] = Math.max(result[0]+nums[i],result[1]);
            result[0] = result[1];
            result[1] = result[2];
        }
        return result[2];
    }
}

错误经验吸取

到了这里,关于198. 打家劫舍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • LeetCode - 198 打家劫舍

    目录 题目来源 题目描述 示例 提示 题目解析 算法源码 题目来源 198. 打家劫舍 - 力扣(LeetCode) 题目描述 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在

    2023年04月08日
    浏览(30)
  • LeetCode198.打家劫舍

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

    2024年03月12日
    浏览(87)
  • LC198. 打家劫舍

     代码随想录

    2024年01月21日
    浏览(58)
  • 力扣 198.打家劫舍【中等】

    题目来源:力扣(LeetCode)https://leetcode.cn/problems/house-robber 题目:你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

    2024年02月16日
    浏览(52)
  • 【LeetCode题目详解】第九章 动态规划part09 198.打家劫舍 213.打家劫舍II 337.打家劫舍III(day48补)

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

    2024年02月09日
    浏览(44)
  • 代码随想录刷题第48天|LeetCode198打家劫舍、LeetCode213打家劫舍II、LeetCode337打家劫舍III

    1、LeetCode198打家劫舍 题目链接:198、打家劫舍 1、dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i] 。 2、递推公式: 如果偷第i房间,那么dp[i] = dp[i - 2] + nums[i] ; 如果不偷第i房间,那么dp[i] = dp[i - 1]; 然后dp[i]取最大值,即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1

    2024年02月08日
    浏览(58)
  • 【LeetCode热题100】198. 打家劫舍(动态规划)

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

    2024年04月11日
    浏览(44)
  • leetcode 343.整数拆分 198.打家劫舍(动态规划)

       OJ链接 :leetcode 343.整数拆分 代码:  OJ链接 :198.打家劫舍    代码:

    2024年02月05日
    浏览(49)
  • 算法刷题Day 48 打家劫舍+打家劫舍II+打家劫舍III

    分成两段来处理:比如说输入的长度是n(0~n-1),就分成[0, n - 1)和[1, n)两部分 写一个辅助函数,返回两个状态,抢或者不抢能得到的最大收获。

    2024年02月16日
    浏览(33)
  • 【算法|动态规划No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年01月20日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包