听：测试开发面试题解（14）- 打家劫舍

测试开发面试题解：打家劫舍问题摘要

本文由何发奋撰写，对“打家劫舍”一题进行了难度分类和算法分析。

难度分类

该问题被归类为简单。

题目描述

题目设计了一个情境，你是一名专业小偷，计划偷窃一排房屋。每家有一定的现金，但不能连续偷窃相邻的房屋，以避免触发连通的防盗系统。目标是在不触发警报的情况下，实现最大的盗窃金额。

示例

通过两个示例展示了问题的具体情况。第一个示例中，最优解是盗窃第1号和第3号房屋，得到的金额为4。第二个示例中，盗窃1号、3号、5号房屋可以获得最高金额12。

算法分析

文章指出，这道题不是简单的求奇数位和偶数位相加的最大值问题。而是通过动态规划来解决，即考虑前n-1家和前n-2家房屋的最大可盗金额。

定义状态dp[i]为遍历到第i个元素时能够偷盗的最大金额。状态转移方程是：当遍历到第i个元素时，若dp[i-2]加上当前房屋金额大于dp[i-1]，则dp[i]更新为dp[i-2]+nums[i]，否则保持dp[i-1]。