打家劫舍

题目要求

这是一个经典的动态规划问题。题目描述了一个小偷在偷窃一排房屋时面临的问题。每个房屋都有一定数量的现金，但是相邻的房屋都有相互连接的防盗系统。如果小偷在同一晚上偷窃了两个相邻的房屋，防盗系统就会触发。小偷的目标是在不触发警报的情况下，从这些房屋中偷取尽可能多的现金。

具体来说，输入是一个非负整数数组，其中每个元素代表一个房屋中的现金数量。需要输出的是小偷在不触发警报系统的情况下，能够偷窃到的最大金额。

解题思路

这个问题可以通过动态规划（Dynamic Programming，DP）来解决。动态规划是一种将复杂问题分解成小问题求解的方法，通常用于求解最优化问题。在这个问题中，我们可以定义一个 DP 数组，其中dp[i]表示到达第i个房屋时，不触发警报装置情况下能偷窃到的最高金额。

我们可以按照以下步骤来构建解决方案：

初始化：创建一个 DP 数组，长度为输入数组的长度加一，dp[0]为 0，因为没有房屋可以偷窃时金额为 0；dp[1]为第一个房屋中的金额，因为开始时只能偷窃第一个房屋。
状态转移方程：对于数组中的每个房屋i（从第二个房屋开始），小偷有两个选择：
- 不偷这个房屋，那么最大金额就是到前一个房屋为止的最大金额，即dp[i-1]；
- 偷这个房屋，那么小偷不能偷前一个房屋，但可以偷前前一个房屋，所以最大金额是当前房屋的金额加上到前前一个房屋为止的最大金额，即nums[i] + dp[i-2]。
对于每个房屋，我们都取这两种选择中的较大值作为dp[i]的值。
状态转移：按照上述状态转移方程，从前向后遍历数组，填充 DP 数组。
输出结果：数组的最后一个元素dp[n]（其中n是输入数组的长度）就是小偷能偷窃到的最大金额。

通过这种方法，我们可以在O(n)的时间复杂度和O(n)的空间复杂度内解决问题。如果需要进一步优化空间复杂度，可以考虑使用滚动数组的方式，只存储必要的几个状态，将空间复杂度降低到O(1)。

Golang 版本

package main

import "fmt"

func rob(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    if n == 1 {
        return nums[0]
    }

    dp := make([]int, n)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i := 2; i < n; i++ {
        dp[i] = max(dp[i-1], dp[i-2]+nums[i])
    }

    return dp[n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    nums := []int{1, 2, 3, 1}
    fmt.Println("Maximum amount that can be robbed is:", rob(nums))
}

这段代码定义了一个rob函数，它接受一个整数数组nums作为输入，返回不触发警报装置情况下能偷窃到的最高金额。main函数中给出了一个示例数组，并打印出调用rob函数的结果。

C++版本

#include <iostream>
#include <vector>
#include <algorithm>

int rob(std::vector<int>& nums) {
    if (nums.empty()) return 0;
    if (nums.size() == 1) return nums[0];

    std::vector<int> dp(nums.size(), 0);
    dp[0] = nums[0];
    dp[1] = std::max(nums[0], nums[1]);

    for (size_t i = 2; i < nums.size(); ++i) {
        dp[i] = std::max(dp[i - 1], dp[i - 2] + nums[i]);
    }

    return dp.back();
}

int main() {
    std::vector<int> nums = {1, 2, 3, 1};
    std::cout << "Maximum amount that can be robbed is: " << rob(nums) << std::endl;
    return 0;
}

这段 C++代码实现了与 Golang 版本相同的逻辑。rob函数接受一个整数类型的vector作为输入，并返回一个整数，表示在不触发警报的情况下，小偷能偷窃到的最大金额。main函数中提供了一个示例数组，并打印出调用rob函数的结果。

Python 版本

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[-1]

if __name__ == "__main__":
    nums = [1, 2, 3, 1]
    print("Maximum amount that can be robbed is:", rob(nums))

这段 Python 代码实现了与前面 Golang 和 C++版本相同的逻辑。rob函数接受一个列表nums作为输入，并返回一个整数，表示在不触发警报的情况下，小偷能偷窃到的最大金额。在__main__部分中，提供了一个示例列表，并打印出调用rob函数的结果。

Java 版本

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

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

        return dp[nums.length - 1];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 2, 3, 1};
        System.out.println("Maximum amount that can be robbed is: " + solution.rob(nums));
    }
}

这段 Java 代码实现了与前面版本相同的逻辑。rob方法接受一个整数数组nums作为输入，并返回一个整数，表示在不触发警报的情况下，小偷能偷窃到的最大金额。main方法中提供了一个示例数组，并打印出调用rob方法的结果。

Rust 版本

fn rob(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    if n == 0 {
        return 0;
    }
    if n == 1 {
        return nums[0];
    }

    let mut dp = vec![0; n];
    dp[0] = nums[0];
    dp[1] = std::cmp::max(nums[0], nums[1]);

    for i in 2..n {
        dp[i] = std::cmp::max(dp[i - 1], dp[i - 2] + nums[i]);
    }

    dp[n - 1]
}

fn main() {
    let nums = vec![1, 2, 3, 1];
    println!("Maximum amount that can be robbed is: {}", rob(nums));
}

这段 Rust 代码实现了与前面版本相同的逻辑。rob函数接受一个整数向量nums作为输入，并返回一个整数，表示在不触发警报的情况下，小偷能偷窃到的最大金额。main函数中提供了一个示例向量，并打印出调用rob函数的结果。

总结

上述问题是一个典型的动态规划问题，其核心思想是通过构建一个数组（或列表）来保存到当前房屋为止能够偷窃到的最大金额。解法的步骤可以总结如下：

边界条件处理：首先处理一些基本情况，例如当没有房屋或只有一个房屋时的情况。
初始化动态规划数组：创建一个动态规划数组dp，其长度与房屋数量相同。dp[i]表示到达第i个房屋时能偷窃到的最大金额。
填充动态规划数组：
- dp[0]被初始化为第一个房屋中的金额。
- dp[1]是第一个房屋和第二个房屋中金额的较大者，因为小偷不能连续偷窃相邻的房屋。
- 对于dp[i]（其中i >= 2），它是以下两个值的较大者：
  - dp[i - 1]，表示如果不偷第i个房屋，那么最大金额就是到前一个房屋为止的最大金额。
  - dp[i - 2] + nums[i]，表示如果偷第i个房屋，那么小偷不能偷第i - 1个房屋，但可以偷第i - 2个房屋，所以最大金额是第i个房屋的金额加上到第i - 2个房屋为止的最大金额。
返回结果：动态规划数组的最后一个元素dp[n - 1]（其中n是房屋的数量）就是小偷能偷窃到的最大金额。

这个解法在不同的编程语言中都有相似的实现，只是语法上有所不同。在 Python、Java 和 Rust 中，都使用了一个数组（或向量）来实现动态规划的存储，并通过迭代来填充这个数组。最终，通过返回数组的最后一个元素来得到最终的答案。

hot-100