首页 > 其他分享 >力扣198.打家劫舍*

力扣198.打家劫舍*

时间:2024-05-02 12:44:54浏览次数:29  
标签:198 nums int 房子 力扣 length 打家劫舍 dp

引言
在做动态规划专题的过程中发现打家劫舍是一个十分经典的动态规划类型题,之后的好多题都有这道题的影子,比如我下一篇准备整理的740.删除并获得点数,弄明白打家劫舍真的可以算是动态规划入门了(所以这个动态规划门槛也太高了吧,我的脑子,我的脑子啊)
题目

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

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

解题思路

198. 打家劫舍 - 力扣(LeetCode)

​ 动态规划

1.定义子问题:从k个房子中能偷到的最大金额,当k==n时就是原问题

2.写出子问题的递推关系:前k个房子的偷法,是偷前k-1个房子或者偷k-2和当前房子,取两种情况下的最大值

3.确定DP数组计算顺序:偷到第k个房子的最大金额取决于k-1和k-2,计算顺序从左到右

代码

class Solution {
    public int rob(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        int length=nums.length;
        int[] dp=new int[length+1];
        //dp[i]代表偷第i个房子,比nums数组下标多一个
        dp[0]=0;
        dp[1]=nums[0];
        for(int i=2;i<=length;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        return dp[length];
    }
}

标签:198,nums,int,房子,力扣,length,打家劫舍,dp
From: https://www.cnblogs.com/always-uie/p/18170104

相关文章

  • 力扣740.删除并获得点数
    题目给你一个整数数组nums,你可以对它进行一些操作。每次操作中,选择任意一个nums[i],删除它并获得nums[i]的点数。之后,你必须删除所有等于nums[i]-1和nums[i]+1的元素。开始你拥有0个点数。返回你能通过这些操作获得的最大点数。解题思路​ 动态规划----打家......
  • 力扣746.使用最小花费爬楼梯
    题目给你一个整数数组cost,其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。你可以选择从下标为0或下标为1的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费解题思路​ 动态规划1.首先需要明确,先支付......
  • 力扣-430. 扁平化多级双向链表
    1.题目题目地址(430.扁平化多级双向链表-力扣(LeetCode))https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list/题目描述你会得到一个双链表,其中包含的节点有一个下一个指针、一个前一个指针和一个额外的子指针。这个子指针可能指向一个单独的双向链表,也......
  • 力扣-82. 删除排序链表中的重复元素
    1.题目题目地址(82.删除排序链表中的重复元素II-力扣(LeetCode))https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/题目描述给定一个已排序的链表的头 head, 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回已排序的链表 。 示例1:......
  • 力扣-83. 删除排序链表中的重复元素
    1.题目题目地址(83.删除排序链表中的重复元素-力扣(LeetCode))https://leetcode.cn/problems/remove-duplicates-from-sorted-list/题目描述给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回已排序的链表 。 示例1:输入:head=[1,1......
  • 力扣-203. 移除链表元素
    1.题目题目地址(203.移除链表元素-力扣(LeetCode))https://leetcode.cn/problems/remove-linked-list-elements/题目描述给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。 示例1:输入:head=[1,2,6,3,4,5,......
  • TODO-力扣-46. 全排列
    1.题目题目地址(46.全排列-力扣(LeetCode))https://leetcode.cn/problems/permutations/题目描述给定一个不含重复数字的数组nums,返回其所有可能的全排列。你可以按任意顺序返回答案。 示例1:输入:nums=[1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,......
  • 力扣-852. 山脉数组的峰顶索引
    1.题目题目地址(852.山脉数组的峰顶索引-力扣(LeetCode))https://leetcode.cn/problems/peak-index-in-a-mountain-array/?envType=study-plan-v2&envId=primers-list题目描述符合下列属性的数组arr称为山脉数组:arr.length>=3存在i(0<i <arr.length-1)使得: ......
  • 力扣-258. 各位相加
    1.题目题目地址(258.各位相加-力扣(LeetCode))https://leetcode.cn/problems/add-digits/?envType=study-plan-v2&envId=primers-list题目描述给定一个非负整数num,反复将各个位上的数字相加,直到结果为一位数。返回这个结果。 示例1:输入:num=38输出:2解释:各位......
  • 力扣-2586. 统计范围内的元音字符串数
    1.题目题目地址(2586.统计范围内的元音字符串数-力扣(LeetCode))https://leetcode.cn/problems/count-the-number-of-vowel-strings-in-range/?envType=study-plan-v2&envId=primers-list题目描述给你一个下标从0开始的字符串数组words和两个整数:left和right。如果字......