LeetCode 198.House Robber (打家劫舍)

小咪咪 2022-04-15 00:49 154阅读 0赞

题目描述：

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

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

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

AC C++ Solution:

典型的动态规划题，第i号房屋的最大金额：dp(i) = max(dp\[i-2\]+nums\[i\], dp\[i-1\])

class Solution {    
    public:
        int rob(vector<int>& nums) {                            //动态规划
            if (nums.size() <= 1)
                return !nums.empty() ? nums[0] : 0; 
            vector<int> dp{nums[0], max(nums[0], nums[1])};     //初始化
            for (int i = 2; i < nums.size(); ++i)
            {
                dp.push_back(max(nums[i] + dp[i - 2], dp[i-1]));    //第i号的最大金额为max(dp[i-2]+nums[i] , dp[i-1]);
            }
            return dp.back();
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode-198. House Robber

Problem: > You are a professional robber planning to rob houses along a street. > Eac

落日映苍穹つ/ 2022年08月20日 12:28/ 0 赞/ 2 阅读

相关 leetCode198-House Robber

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

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

相关 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 赞/ 145 阅读

相关 LeetCode198—House Robber

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

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

相关 [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 赞/ 138 阅读

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

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

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

相关 [LeetCode] House Robber 打家劫舍

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

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

相关 LeetCode 198.House Robber (打家劫舍)

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

小咪咪/ 2022年04月15日 00:49/ 0 赞/ 155 阅读

相关（Java）leetcode-198 House Robber（打家劫舍）

更多LeetCode题解，可移步[我的解题记录][Link 1]，持续更新中~ 题目描述你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的

客官°小女子只卖身不卖艺/ 2022年03月06日 12:08/ 0 赞/ 194 阅读

相关 198. House Robber

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

た入场券/ 2022年03月02日 08:10/ 0 赞/ 194 阅读