DataStructure_Algorithm_HandBook_PreForLeetCode

198. House Robber

Solved

Medium

Topics

Companies

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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return 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:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

solution

对于任意一个房子，可能性只有两种，如果偷了x处的房子，那么就不能偷下一家，如果不偷，那么就是可以下一家

考虑 f（i） ，从第 i 位往后考虑，能获得的最大价值是多少。

选 和 不选

f(i) = max(f(i+1), f(i+2)+n(i));

递归终止条件：如果当前 index 超过或等于房子数量，返回 0。 递归选择：在每一步中，有两种选择： 不偷当前房子，继续考虑下一个房子 (dfs(index + 1, nums)）。 偷当前房子，并跳过下一个房子，继续考虑再下一个房子 (dfs(index + 2, nums) + nums[index])。 选择最大值：在两种选择中取最大值。

由于存在大量重复计算，时间复杂度很高，达到 O(2^n)，其中 n 是房子的数量。

可以先把， 递归（Recursive Algorithm） 的版本写出来， 然后测试一下样例是不是都能过，如果都可以的话，再加上记忆化搜索的步骤。

class Solution {
    public int rob(int[] nums) {
       return  dfs(0,nums);
    }
    int dfs(int index, int[] nums){
        if(index >= nums.length) return 0;
        return Math.max(dfs(index+1,nums),dfs(index+2,nums)+nums[index]);
    }
}

为了优化原始版本，我们使用记忆化递归。记忆化递归是一种自顶向下的动态规划方法，通过存储已经计算过的结果来避免重复计算。优化的算法逻辑如下：

递归终止条件：与原始版本相同。 检查记忆数组：在计算之前，首先检查记忆数组 memo，如果当前 index 已经计算过，则直接返回存储的结果。 存储计算结果：在进行递归计算后，将结果存储在记忆数组 memo 中。 选择最大值：与原始版本相同。

var rob = function(nums) {
    let memo = new Array(nums.length).fill(-1);
    return dfs(0, nums, memo);
};

function dfs(index, nums, memo) {
    if (index >= nums.length) return 0;
    if (memo[index] !== -1) return memo[index];
    
    memo[index] = Math.max(dfs(index + 1, nums, memo), dfs(index + 2, nums, memo) + nums[index]);
    return memo[index];
}