house-robber

House Robber – LeetCode 198

Problem

Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Answer

Original

Code

class Solution {
public:
    int rob(vector<int>& nums) {
        int a = 0, b = 0;
        for(unsigned i = 0; i != nums.size(); ++i){
            if(i % 2 == 0){
                a = max(a+nums[i],b);
            }else{
                b = max(b+nums[i],a);
            }
        }
        return max(a,b);
    }
};

思路

使用DP，递推公式为dp[i] = max(num[i] + dp[i - 2], dp[i - 1])，有趣的是实现使用两步走的方式来缓存i-1和i-2元素，减少了数组的空间开销，时间复杂度$O(n)$，空间复杂度$O(1)$。

Better

没看到更好的。昨天晚上ACM校赛只拿到了44名，惭愧。电力和材料的两个大佬分别拿到了13和22名，接下来还需要学习《算法导论》，路依旧很长。