LeetCode198 打家劫舍

house-robber

Difficulty: 简单

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

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

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

Solution

Language: C++

动态规划

class Solution {
public:
    int rob(vector<int>& nums) {
        int size = nums.size();
        if (size == 0) return 0;
        // 二维数组 代表某一天偷或者不偷获利的最高金额
        vector<vector<int>> dp(size,vector<int>(2,0));
        // [x][0] 不偷
        // [x][1] 偷
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for (int i =1;i<size;i++) {
            // 当前不偷的最大值 等于 (上一个偷的最大值 或者上一次不偷的最大值)
            // 取两个选择的最大值
            dp[i][0] = max(dp[i-1][1],dp[i-1][0]); 
            // 当前偷的最大值等于上一个不偷的最大值
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        int maxVal = max(dp[size-1][0],dp[size-1][1]);
        return maxVal;
    }
};

时间复杂度: O(n)
空间复杂度: O(n)

动态规划-优化版

class Solution {
public:
    int rob(vector<int>& nums) {
        int size = nums.size();
        if (size == 0) return 0;
        // 不偷
        int dp1 = 0; 
        // 偷
        int dp2 = nums[0];
        for (int i =1;i<size;i++) {
            int temp = dp1;
            // 不偷
            dp1 = max(temp,dp2);
            // 偷 = 上一个不偷
            dp2 = temp + nums[i];
        }
        return max(dp1,dp2);
    }
};

时间复杂度: O(n)
空间复杂度: O(1)
和上一个不同的是, 后一个dp的值仅仅与上一个dp有关,所以不需要二维数组存储

leetcode提交时发现,临时变量在for循环内部声明的效率比在外部声明要高得多, 推测是因为内存的就近访问缓存的原因.

递归与记忆

class Solution {
public:
    int rob(vector<int>& nums) {
        int size = nums.size();
        if (size == 0) return 0;
        vector<int> robs = vector<int>(size,-1);
        return rob(nums,robs,size - 1);
    }
private:
    int rob(vector<int>& nums,vector<int> &robs,int maxIndex) {
        if (maxIndex < 0) return 0;
        // 这里有个判断问题超时了, 可能偷取的金额为0, 所以这里要增加判断 >=0 ,而不是 0
        if (robs[maxIndex] >= 0) return robs[maxIndex];
        robs[maxIndex] = max(rob(nums,robs,maxIndex-2) + nums[maxIndex],rob(nums,robs,maxIndex-1));
        return robs[maxIndex];
    }
};