198.house-robber.cpp

/*
 * @lc app=leetcode id=198 lang=cpp
 *
 * [198] House Robber
 *
 * https://leetcode.com/problems/house-robber/description/
 *
 * algorithms
 * Medium (42.67%)
 * Likes:    6577
 * Dislikes: 187
 * Total Accepted:    679.5K
 * Total Submissions: 1.6M
 * Testcase Example:  '[1,2,3,1]'
 *
 * 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.
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: nums = [1,2,3,1]
 * Output: 4
 * Explanation: Rob house 1 (money = 1) and then rob house 3 (money =
 * 3).
 * Total amount you can rob = 1 + 3 = 4.
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: nums = [2,7,9,3,1]
 * Output: 12
 * Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house
 * 5 (money = 1).
 * Total amount you can rob = 2 + 9 + 1 = 12.
 * 
 * 
 * 
 * Constraints:
 * 
 * 
 * 0 <= nums.length <= 100
 * 0 <= nums[i] <= 400
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    public:
    int rob1(vector<int>& nums) {
        if (nums.size() == 0)
            return 0;
        int n = nums.size();
        vector<int> dp(n, 0);
        
        for (int i = 0; i < n; ++i) {
            if (i >= 2) {
                dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
            } else if (i >= 1) {
                dp[i] = max(nums[i], dp[i - 1]);
            } else 
                dp[i] = nums[i];
        }
        return dp[n - 1];
    }
    
    int rob(vector<int>& nums) {
        int a = 0, b = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int first = max(b + nums[i], a);
            b = a;
            a = first;
        }
        return a;
    }
};
// @lc code=end