C语言重构【198】打家劫舍

﹏ヽ暗。殇╰゛Y 2022-12-16 13:23 128阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
    
    给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
    
     
    
    示例 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 。
     
    
    提示：
    
    0 <= nums.length <= 100
    0 <= nums[i] <= 400

#### 方案： ####

*  动态规划

#include <iostream>
    #include <vector>
    using namespace ::std;
    class Solution { 
    public:
        int rob(vector<int>& nums) { 
            int len = nums.size();
            // vector<int>res{nums[0],nums[1]};
            vector<int>res(len,0);
            res[0]=nums[0];
            res[1]=max(nums[0],nums[1]);
            for(int i = 2;i<len;i++){ 
                res[i]= max(nums[i]+res[i-2],res[i-1]);
            }
            return res[len-1];
        }
    };
    
    int main(){ 
        Solution s;
        // vector<int> nums{1,2,3,1};
        // vector<int> nums{2,7,9,3,1};
        vector<int> nums{ 2,1,1,2};
        cout<< s.rob(nums);
    }

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode