多味的LeetCode --- 198. 打家劫舍

向右看齐 2023-02-21 06:25 14阅读 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 。

--------------------

**解题思路1:**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70]

--------------------

**代码1：**

**python写法：**

import numpy as np
    class Solution(object):
        def rob(self, nums):
            n = len(nums)
            
            f = np.zeros(n+1, dtype = int)
            g = np.zeros(n+1, dtype = int)
    
            for i in range(1, n+1):
                f[i] = max(f[i-1], g[i-1])
                g[i] = nums[i-1] + f[i-1]  # 第i个数在nums中是i-1,nums中的小标从0开始
    
            return max(f[n], g[n])

**C++写法：**

class Solution {
        
    public:
        int rob(vector<int>& nums) {
        
            int n = nums.size();
            vector<int> f(n+1),g(n+1);
            for(int i = 1; i <= n; i++){
        
                f[i] = max(f[i-1], g[i-1]);
                g[i] = nums[i-1] + f[i-1];
            }
            return max(f[n], g[n]);
        }
    };

--------------------

**参考链接:**

[https://www.bilibili.com/video/BV15441117yb?from=search&seid=16255148537935748434][https_www.bilibili.com_video_BV15441117yb_from_search_seid_16255148537935748434]

--------------------

**题目来源：**

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200701090119662.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70
[https_www.bilibili.com_video_BV15441117yb_from_search_seid_16255148537935748434]: https://www.bilibili.com/video/BV15441117yb?from=search&seid=16255148537935748434
[https_leetcode-cn.com_problems_house-robber]: https://leetcode-cn.com/problems/house-robber