Leetcode刷题java之198. 打家劫舍

向右看齐 2024-04-17 17:05 11阅读 0赞

执行结果：

通过

显示详情

执行用时 :1 ms, 在所有 Java 提交中击败了95.89%的用户

内存消耗 :34.7 MB, 在所有 Java 提交中击败了84.09%的用户

题目：

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

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

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/house-robber  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

这道题和最小花费爬楼梯是类似的，这道题也要求递推公式

[最小花费爬楼梯][Link 1]

不同的是这道题跳的是两个或者三个

比如：

当前金额是f（n），他不能从前一个来，会触发报警

他只能从前前一个或者前前前一个来，而且要从他们之间较大的来

那么就可以求出递推公式

f（n）=max（f（n-2），f（n-3））+nums\[ n \]

如果你还是看不懂的话，可以按照示例里的例子走一遍应该明白其中的道理了

代码：

class Solution {
        public int rob(int[] nums) {
            //由于要处理递推公式，递推公式要有-2和-3，所以要先把前三项进行处理一下，再进行计算
            if(nums.length==0)
            {
                return 0;
            }
            if(nums.length==1)
            {
                return nums[0];
            }
            if(nums.length==2)
            {
                return Math.max(nums[0],nums[1]);
            }
            if(nums.length==3)
            {
                return Math.max(nums[0]+nums[2],nums[1]);
            }
            int len=nums.length;
            int[] result=new int[len];
            result[0]=nums[0];
            result[1]=nums[1];
            result[2]=nums[2]+nums[0];
            for(int i=3;i<len;i++)
            {
                result[i]=Math.max(result[i-2],result[i-3])+nums[i];
            }
            return Math.max(result[len-1],result[len-2]);
        }
    }

[Link 1]: https://blog.csdn.net/qq_41901915/article/details/100129911