【华为OD技术面试手撕真题】39、打家劫舍 | 手撕真题+思路参考+代码解析（C & C++ & Java & Python & JS） （0ms）

华为OD技术面试手撕真题：打家劫舍

在华为的OD技术面试中，常常会遇到一些经典的算法题。其中，关于“打家劫舍”的问题，就是一道非常常见的动态规划题。这道题的核心思想是通过选择性地“打劫”房屋，以最大化所盗取的财物总值，而又不触发报警系统。

题目描述

假设有一排房屋，每个房屋内都有一定数量的现金，且相邻的房屋不能同时被打劫。要求在不打劫相邻房屋的前提下，计算可以偷取的最大总金额。

给定一个数组 nums，数组中的每个元素代表对应房屋中的现金数额。返回可以盗取的最大现金数额。

例如： 输入：nums = [2, 7, 9, 3, 1] 输出：12 （偷取第 1、3、5 幢房屋中的现金，2+9+1=12）

思路分析

1. 动态规划：可以定义一个一维数组 dp，其中 dp[i] 表示偷取第 i 个房屋所能获得的最大现金数额。根据偷取策略的不同，我们可以有以下状态转移方程：
2. 对于第 i 个房屋：
   • 如果选择打劫这个房屋，则不能打劫第 i-1 个房屋，最大值为 nums[i] + dp[i-2]。
   • 如果不打劫这个房屋，则最大值为 dp[i-1]。

3. 因此，状态转移方程为： [ dp[i] = \max(dp[i-1], nums[i] + (i > 1 ? dp[i-2] : 0)) ]

4. 边界条件：

5. 如果只有一个房屋，偷取的最大现金为它本身的现金数。

6. 如果有两个房屋，偷取的最大现金为两者中的较大值。

7. 空间优化：由于只用到了前两个状态的缓存，可以使用两个变量来代替数组，从而降低空间复杂度。

代码示例

以下是用 Python 实现的该算法：

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

    prev1, prev2 = 0, 0

    for num in nums:
        temp = prev1
        prev1 = max(prev2 + num, prev1)
        prev2 = temp

    return prev1

# 测试
nums = [2, 7, 9, 3, 1]
print(rob(nums))  # 输出 12

C++ 实现

#include <vector>
#include <algorithm>
using namespace std;

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

    int prev1 = 0, prev2 = 0;

    for (int num : nums) {
        int temp = prev1;
        prev1 = max(prev2 + num, prev1);
        prev2 = temp;
    }

    return prev1;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为房屋的数量。
• 空间复杂度：O(1)，只使用了常量大小的额外空间。

总结

“打家劫舍”问题是一个经典的动态规划问题，通过合理的状态转移和边界条件，可以有效地求解出最大可偷金额。掌握这样的题目不仅帮助我们在面试中脱颖而出，还能加深我们对动态规划思想的理解。希望以上分析与代码示例能够帮助你更好地理解这个问题及其解决方案。