198.house-robber.en.md

House Robber

https://leetcode.com/problems/house-robber/description/

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.

Example 1:

Input: [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: [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.

Prerequisites

• Dynamic Programming

Solution

This is a simple and classical dynamic programming problem, but it's helpful for understanding dynamic programming.

Frequent questions when it comes to DP problems involve:

1. Why the solution works like that? Why it works without any DP array?
2. Why we can apply the idea of Fibonacci Numbers to the Climbing Stairs problem?

We will take a look at these problems here. Similar to other DP problems, we are essentially deciding whether rob the i^th house or not.

If we rob the i^th house, the gain would be nums[i] + dp[i - 2].

We cannot rob i-1^th house, otherwise the alarm will be triggered.

If we do not rob the i^th house, the gain would be dp[i - 1].

The dp here is our subproblem.

Since we always want a larger gain, it's easy to obtain the transition formula: dp[i] = Math.max(dp[i - 2] + nums[i - 2], dp[i - 1]);

Note: For the convenience of calculation, we set both dp[0] and dp[1] to be 0. This way, dp[i] is actually for the i-1^th house.

We can use the following graph to illustrate the above process:

If we optimize it further, we only need dp[i - 1] and dp[i - 2] when determining each dp[i]. For example, to calculate dp[6], we would only need dp[5] and dp[4], and there's no need to keep dp[3], dp[2], and so on, in memory.

Then, the code will be:

let a = 0;
let b = 0;

for (let i = 0; i < nums.length; i++) {
  const temp = b;
  b = Math.max(a + nums[i], b);
  a = temp;
}

return b;

The above code optimized the space complexity from O(n) to O(1). The same optimization applies to a lot of DP problems.

Key Points

Code (JS/C++/Python)

JavaScript Code：

/*
 * @lc app=leetcode id=198 lang=javascript
 *
 * [198] House Robber
 *
 * https://leetcode.com/problems/house-robber/description/
 *
 * algorithms
 * Easy (40.80%)
 * Total Accepted:    312.1K
 * Total Submissions: 762.4K
 * 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: [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: [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.
 *
 *
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  // Tag: DP
  const dp = [];
  dp[0] = 0;
  dp[1] = 0;

  for (let i = 2; i < nums.length + 2; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i - 2], dp[i - 1]);
  }

  return dp[nums.length + 1];
};

C++ Code：

This is slightly different from the JavaScript solution, but it uses the same transition function.

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        auto sz = nums.size();
        if (sz == 1) return nums[0];
        auto prev = nums[0];
        auto cur = max(prev, nums[1]);
        for (auto i = 2; i < sz; ++i) {
            auto tmp = cur;
            cur = max(nums[i] + prev, cur);
            prev = tmp;
        }
        return cur;
    }
};

Python Code:

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0

        length = len(nums)
        if length == 1:
            return nums[0]
        else:
            prev = nums[0]
            cur = max(prev, nums[1])
            for i in range(2, length):
                cur, prev = max(prev + nums[i], cur), cur
            return cur