【力扣hot100】 198. 打家劫舍

张开发
• 2026/4/5 18:33:57 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【力扣hot100】 198. 打家劫舍
一、题目你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统 如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组 计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 示例 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 。 提示 1 nums.length 100 0 nums[i] 400二、思路中等题但也是很简单的动态规划。既然不能选择相邻的两数那就内层循环 dp[0 到 i-2]寻找加上自己的最大金额。这样就能覆盖中间故意不偷的选择然后用ans存储最大的dp[i]即可。三、题解class Solution { public: int rob(vectorint nums) { vectorint dp(nums.size(),0); int ans0; dp[0]nums[0]; if(nums.size()1) return dp[0]; dp[1]max(nums[1],dp[0]); ansmax(dp[0],dp[1]); for(int i2;inums.size();i){ for(int j0;ji-1;j){ dp[i]max(dp[i],dp[j]nums[i]); } ansmax(ans,dp[i]); } return ans; } };

更多文章