[LeetCode每日1题][简单] 198. 打家劫舍 / 面试题 17.16.按摩师

文章目录

• 题目
• 动态规划解法
• 复杂度

题目

俩题是一样的

面试题 17.16. 按摩师 - 力扣（LeetCode）
198. 打家劫舍 - 力扣（LeetCode）

动态规划解法

dp值表示到目前为止可以收获的最高金额，到一个新房屋i时，有两种选择

• 偷窃，该点dp值等于该点金额+dp[i-2]
• 不偷窃，该点dp值等于dp[i-1]

选收益最大的那个即可。

dp值可以存在数组里，注意到我们只需要i-2和i-1号的dp值，所以可以优化成用两个变量存。

class Solution {
    public:
    int massage(vector<int>& nums) {
        if(nums.empty()) return 0;
        if(nums.size() == 1) return nums[0];
        int dp0 = nums[0];
        int dp1 = max(dp0,nums[1]);
        for(int i = 2; i < nums.size(); i++){
            int dp2 = max(dp0 + nums[i], dp1);
            dp0 = dp1;
            dp1 = dp2;
        }
        return dp1;
    }
};

复杂度

O(N)时间，O(1)空间