LeetCode题解198.house-robber

题目地址

https://leetcode.com/problems/house-robber/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.

思路

这是一道非常典型且简单的动态规划问题，但是在这里我希望通过这个例子，
让大家对动态规划问题有一点认识。

为什么别人的动态规划可以那么写，为什么没有用 dp 数组就搞定了。
比如别人的爬楼梯问题怎么就用 fibnacci 搞定了？为什么？在这里我们就来看下。

思路还是和其他简单的动态规划问题一样，我们本质上在解决对于第[i] 个房子，我们抢还是不抢。的问题。

判断的标准就是总价值哪个更大， 那么对于抢的话就是当前的房子可以抢的价值 + dp[i - 2]

i - 1 不能抢，否则会触发警铃

如果不抢的话，就是dp[i - 1].

这里的 dp 其实就是子问题.

状态转移方程也不难写dp[i] = Math.max(dp[i - 2] + nums[i - 2], dp[i - 1]);（注：这里为了方便计算，令 dp[0]和 dp[1]都等于 0，所以 dp[i]对应的是 nums[i - 2]）

上述过程用图来表示的话，是这样的：

我们仔细观察的话，其实我们只需要保证前一个 dp[i - 1] 和 dp[i - 2] 两个变量就好了，
比如我们计算到 i = 6 的时候，即需要计算 dp[6]的时候， 我们需要 dp[5], dp[4]，但是我们
不需要 dp[3], dp[2] ...

因此代码可以简化为：

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;

如上的代码，我们可以将空间复杂度进行优化，从 O(n)降低到 O(1),
类似的优化在 DP 问题中不在少数。

动态规划问题是递归问题查表，避免重复计算，从而节省时间。
如果我们对问题加以分析和抽象，有可能对空间上进一步优化

关键点解析

代码

• 语言支持：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：

与JavaScript代码略有差异，但状态迁移方程是一样的。

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

LeetCode题解 缺失的第一个正数

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。示例 1:输入: [1,2,0]输出: 3示例 2:输入: [3,4,-1,1]输出: 2示例 3:输入: [7,8,9,11,12]输出: 1说明:你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。题解：数组arr长度为len，要找到最小正整数x，x 肯定在[1, len + 1]之间，…

LeetCode题解15.3-sum

题目地址 https://leetcode.com/problems/3sum/description/ 题目描述 Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in…

LeetCode题解213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。示例 1:输入: [2,3…

LeetCode题解152.maximum-product-subarray

题目地址 https://leetcode.com/problems/maximum-product-subarray/description/ 题目描述 Given an integer array nums, find the contiguous subarray within an array (containing at least one num…

LeetCode题解128.longest-consecutive-sequence

题目地址 https://leetcode.com/problems/longest-consecutive-sequence/description/ 题目描述 Given an unsorted array of integers, find the length of the longest consecutive elements sequence.…