leetcode House Robber

快来打我* 2022-08-01 11:08 151阅读 0赞

# 题目 #

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

题目来源：[https://leetcode.com/problems/house-robber/][https_leetcode.com_problems_house-robber]

# 分析 #

动态规划，一维辅助数组dp。dp\[i\]表示从第i个元素开始往右，所能抢劫到的最大财富值（抢劫了第i个）。从右往左遍历，dp\[i\] = nums\[i\] + max(dp\[i+2\], dp\[i+3\]…dp\[len-1\])。可以设置一个辅助变量，维护自dp\[i+2\]往右的最大值，省得每次都求了。  
还可以优化一下空间，我觉得可以不用一维辅助数组，用三个变量就行了。

# 代码 #

class Solution {
    public:
        int rob(vector<int>& nums) {
            int size = nums.size();
            if(size == 0)
                return 0;
            vector<int> dp(size + 1, 0);
            dp[size-1] = nums[size-1];
            int ans = dp[size - 1];
            int max_next = 0;
            for(int i = size - 2; i >= 0; i--){
                dp[i] = nums[i] + max_next;
                ans = max(ans, dp[i]);
                max_next = max(dp[i+1], max_next);
            }
            return ans;
        }
    };

[https_leetcode.com_problems_house-robber]: https://leetcode.com/problems/house-robber/

发表评论取消回复

表情：

评论列表（有 0 条评论，151人围观）

还没有评论，来说两句吧...

相关阅读

相关 House Robber--LeetCode

You are a professional robber planning to rob houses along a street. Each house has a ce

本是古典何须时尚/ 2022年08月07日 13:52/ 0 赞/ 15 阅读

相关 leetCode198-House Robber

题目： You are a professional robber planning to rob houses along a street. Each house has

今天药忘吃喽~/ 2022年08月07日 10:55/ 0 赞/ 149 阅读

相关 [LeetCode] House Robber

House Robber You are a professional robber planning to rob houses along a street.

ゝ一世哀愁。/ 2022年08月05日 01:00/ 0 赞/ 150 阅读

相关 leetcode House Robber II

题目 Note: This is an extension of House Robber. After robbing those houses on that st

小鱼儿/ 2022年08月01日 11:08/ 0 赞/ 137 阅读

相关 leetcode House Robber

题目 You are a professional robber planning to rob houses along a street. Each house ha

快来打我*/ 2022年08月01日 11:08/ 0 赞/ 152 阅读

相关 leetcode 198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a ce

旧城等待，/ 2022年07月28日 01:09/ 0 赞/ 162 阅读

相关 LeetCode198—House Robber

原题 [原题链接][Link 1] You are a professional robber planning to rob houses along a stre

傷城~/ 2022年07月11日 12:22/ 0 赞/ 143 阅读

相关 [leetcode]: 198. House Robber

1.题目 You are a professional robber planning to rob houses along a street. Each house

ゞ浴缸里的玫瑰/ 2022年06月15日 09:14/ 0 赞/ 150 阅读

相关 [LeetCode] House Robber 打家劫舍||

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系

怼烎@/ 2022年05月18日 07:57/ 0 赞/ 168 阅读

相关 [LeetCode] House Robber 打家劫舍

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

- 日理万妓/ 2022年05月18日 02:57/ 0 赞/ 175 阅读