校招算法面试-打家劫舍(一)

打家劫舍（一）的动态规划解法

本题要求在不偷取相邻房屋的前提下，计算能偷取的最大金额。动态规划是解决此类问题的有效方法，通过构建状态转移方程逐步求解。

方法思路

定义状态：dp[i]表示前i个房屋能偷取的最大金额。
初始状态：
dp[0] = 0：没有房屋时，金额为0。
dp[1] = nums[0]：只有一个房屋时，只能偷它。
状态转移：
对于第i个房屋，有两种选择：
偷：则不能偷第i-1个房屋，最大金额为nums[i-1] + dp[i-2]。
不偷：最大金额为dp[i-1]。
转移方程：dp[i] = max(dp[i-1], nums[i-1] + dp[i-2])。

解决代码class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 n = len(nums) if n == 1: return nums[0] dp = [0] * (n + 1) dp[1] = nums[0] for i in range(2, n + 1): dp[i] = max(dp[i-1], nums[i-1] + dp[i-2]) return dp[n]代码解释

初始检查：如果输入数组为空，直接返回0。
单元素处理：若只有一个房屋，直接返回该房屋的金额。
初始化DP数组：dp数组长度为n+1，dp[1]初始化为第一个房屋的金额。
动态规划填充：从第二个房屋开始遍历，根据状态转移方程更新dp[i]，即比较偷与不偷当前房屋的金额，取较大值。
返回结果：dp[n]即为前n个房屋能偷取的最大金额。

此方法确保在O(n)时间内解决问题，空间复杂度为O(n)，适用于中等规模的数据。

您可能感兴趣问答

Collapsible

热门标签

热点问答