Description Link to heading

198.house-robber

Solution Link to heading

dp[i] denotes the maximum amount when the first i houses are considered.

Let’s consider the recursive relationship:

  • If the i-th house was stolen, it means that the i - 1th house was not stolen, so dp[i] = dp[i - 2] + a[i - 1].
  • If the i-th house was not stolen, then dp[i] = dp[i - 1].

So, dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1]).

Code Link to heading 

#include <vector>
using std::vector;
class Solution {
  private:
    int max(int a, int b) {
        return a > b ? a : b;
    }

  public:
    int rob(vector<int> &nums) {
        vector<int> dp(nums.size() + 1, 0);
        if (nums.size() == 1)
            return nums[0];
        if (nums.size() == 2)
            return nums[0] > nums[1] ? nums[0] : nums[1];
        dp[1] = nums[0];
        for (int i = 2; i <= nums.size(); i++) {
            dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1]);
        }
        return dp[nums.size()];
    }
};