代码编织梦想

题目描述:

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

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

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

提示:

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

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

题目描述:

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

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

示例 1:

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

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

输入:nums = [0]
输出:0

提示:

1 <= nums.length <= 100
0 <= nums[i] <= 1000

class Solution {
    public int rob(int[] nums) {
        if(nums==null||nums.length==0)
            return 0;
        if(nums.length==1)
            return nums[0];
        if(nums.length==2)
            return Math.max(nums[0],nums[1]);
        else 
            return Math.max(range(nums,0,nums.length-2),range(nums,1,nums.length-1));
    }

    public int range(int[] nums,int start,int end)
    {
        int[] dp=new int[end-start+1];
        for(int i=start;i<=end;i++)
        {
            if(i==start)
                dp[i-start]=nums[start];
            else if(i==start+1)
                dp[i-start]=Math.max(nums[start],nums[i]);
            else
                dp[i-start]=Math.max(dp[i-2-start]+nums[i],dp[i-1-start]);
        }
        return dp[end-start];
    }
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39622795/article/details/115738417

leetcode-198. 打家劫舍-java_wangxizzz的博客-爱代码爱编程

LeetCode-198 House Robber 问题描述 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被

leetcode213——打家劫舍ii_清風逐尘乀的博客-爱代码爱编程_打家劫舍二

我的LeetCode代码仓:https://github.com/617076674/LeetCode 原题链接:https://leetcode-cn.com/problems/house-robber-ii/description/ 题目描述: 知识点:动态规划 思路:两次LeetCode198——打家劫舍 第一个房屋和最后一个房屋是紧挨

leetcode-198. 打家劫舍_ガッシュ·ベル的博客-爱代码爱编程_打家劫舍 领扣

198. House Robber You are a professional robber planning to rob houses along a street. Each house has a certain

leetcode--198 打家劫舍_courage-hu的博客-爱代码爱编程

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

leetcode-198. 打家劫舍、213. 打家劫舍 ii-爱代码爱编程

  目录 198. 打家劫舍 213. 打家劫舍 II 198. 打家劫舍 【题目】:   【方法1】:动态规划(比较好理解,重点掌握) 从后往前抢,抢到 i 时,dp[i] 的值等于 max{抢劫 i 号房子,不抢劫 i }。 抢劫 i ,i 后面最大利益为 dp[i-2]+nums[i]不抢劫 i ,i 后面最大利益为 dp[i

leetcode ---- 198. 打家劫舍 (java)_ziqiiii的博客-爱代码爱编程

动态规划: 取舍问题 开辟f[n]数组,保存当前偷窃前n个房屋的最大金额。   1. 最后状态,f[n]的值,可以对nums[n]取或者不取 2. 转移方程为:f[n] = max( f[n-1], f[n-2] + nums[n])  // 不取,取 , n>=2 3. 初始条件: f[0] = nums[0], f[1] =

leetcode--打家劫舍-爱代码爱编程

打家劫舍 动态规划的又一道基础题,先分析问题子结构,再列公式。 问题描述 小偷进行偷窃,不能偷窃相邻的两个房间,不然会触发报警,请问怎样才能窃取到最大的金额。 金额数字用数组表示 [1, 2, 3, 1] 问题分析 要首先看一个问题能不能由他的子问题进行解决 可以:能用动态规划;不可以:不能用动态规划解决。 假设一共有n个

LeetCode-198-打家劫舍-爱代码爱编程

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 示例 1: 输入:[1,2,3,1] 输出:4 解释

leetcode-198、213、337:打家劫舍-爱代码爱编程

目录 leetcode-198 打家劫舍(常规dp)leetcode-213. 打家劫舍 II(环形)leetcode-337. 打家劫舍 II(二叉树) 递归超时增加备忘录 leetcode-198 打家劫舍(常规dp) 思路:动态规划状态: dp(n) 表示0到n的最大打劫数量转移: 打劫这个:dp(n-2)+nums[n], 不打劫

Leetcode----213打家劫舍||+198打家劫舍|-爱代码爱编程

今天的每日一题是《打家劫舍||》,先找到《打家劫舍|》做一下,熟悉一下题目。 打家劫舍| 解题思路 简单的动态规划问题,找到规律就非常简单,但是题目的范围给挖了一个坑,需要注意规避(数组的长度是从0开始的,所以要对数组长度为0的情况进行处理,虽然我没尝试不处理会怎么样,但是也应该注意到这个问题)。 因为不能偷连续的两个房子的财物,所以对于数

leetcode-198:打家劫舍-爱代码爱编程

题目描述 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 示例 1: 输入:[1,2,3,1] 输出:

LeetCode-198-打家劫舍 C++-爱代码爱编程

LeeCode-198-打家劫舍思路+代码 思路+代码解析状态转移方程递归算法DP算法+输出抢的房屋号main 思路+代码解析 状态转移方程 1、如果只有一家的话,就只能抢这一家,即最优解。 2、如果只有两家的话,最优解为这两家钱最多的一家 3、如果有多于两家的话,关键点为第(n-1)家。如果抢了第(n-1)家,说明在前(n-1)家里已经求

LeetCode-198 打家劫舍-爱代码爱编程

LeetCode-198 打家劫舍 考察内容: 数组、动态规划 题目描述: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内

力扣 206.翻转链表-爱代码爱编程

文章目录 题目链接源代码 github 地址1、题目要求2、思路分析(双指针法解决)3、执行代码 - Java4、问题反思5、小结 题目链接 https://leetcode-cn.com/problems/reverse-linked-list/ 源代码 github 地址 https://github.com/YIME

139-单词拆分-爱代码爱编程

题目 给你一个字符串 s 和一个字符串列表 wordDict 作为字典,判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。 说明:拆分时可以重复使用字典中的单词。 示例 1: 输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode”

LeetCode 24. Swap Nodes in Pairs - 链表(Linked List)系列题5-爱代码爱编程

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves ma