环形房屋如何 “安全劫舍”？动态规划解题逻辑与技巧

环形房屋如何 “安全劫舍”？动态规划解题逻辑与技巧

• 1、问题描述
• 2、解题思路
• 3、动态规划解法
  • 3.1 辅助函数
  • 3.2 主函数
• 4、代码解析
• 5、复杂度分析
• 6、测试用例
• 7、关键点总结
• 8、常见问题解答

1、问题描述

你是一个专业的小偷，计划偷窃环形排列的房屋。每间房屋都有一定金额，但如果偷窃相邻的两间房屋就会触发警报。计算在不触发警报的情况下能够偷窃到的最高金额。

2、解题思路

这个问题是经典打家劫舍问题的变种，房屋排列成环形。我们可以将其分解为两个子问题：

1. 不偷第一间房屋
2. 不偷最后一间房屋
   然后取这两个子问题的最大值作为最终结果。

3、动态规划解法

3.1 辅助函数

首先实现一个标准的打家劫舍函数，处理线性排列的房屋：

introbLinear(int* nums,int start,int end){int prev =0, curr =0;for(int i = start; i < end; i++){int temp = curr; curr =(prev + nums[i]> curr)? prev + nums[i]: curr; prev = temp;}return curr;}

3.2 主函数

处理环形排列的情况：

introb(int* nums,int numsSize){if(numsSize ==0)return0;if(numsSize ==1)return nums[0];// 两种情况：不偷第一间或不偷最后一间int option1 =robLinear(nums,0, numsSize -1);int option2 =robLinear(nums,1, numsSize);return(option1 > option2)? option1 : option2;}

4、代码解析

1. 边界条件处理：
   • 空数组返回0
   • 只有一间房屋直接返回该房屋金额
2. 分解问题：
   • option1：不偷最后一间房屋（即考虑从第1间到倒数第2间）
   • option2：不偷第一间房屋（即考虑从第2间到最后1间）
3. 动态规划核心：
   • prev和curr分别记录前一步和当前的最大金额
   • 对于每间房屋，选择偷或不偷的最大值

5、复杂度分析

• 时间复杂度：O(n)，只需两次线性遍历
• 空间复杂度：O(1)，只使用常数空间

6、测试用例

intmain(){int nums1[]={2,3,2};printf("%d\n",rob(nums1,3));// 输出3int nums2[]={1,2,3,1};printf("%d\n",rob(nums2,4));// 输出4int nums3[]={1,2,3};printf("%d\n",rob(nums3,3));// 输出3return0;}

7、关键点总结

1. 问题分解：将环形问题分解为两个线性问题
2. 动态规划：使用标准打家劫舍的解法处理线性情况
3. 空间优化：只用两个变量存储中间结果，无需完整DP数组
4. 边界处理：正确处理空数组和单元素数组的情况

8、常见问题解答

Q: 为什么分解为两个子问题？
A: 因为第一间和最后一间不能同时偷，所以要么不偷第一间，要么不偷最后一间。

Q: 如何保证不偷相邻房屋？
A: 动态规划中总是比较偷当前房屋和不偷当前房屋的较大值。

Q: 这个方法能处理所有情况吗？
A: 是的，这种方法能正确处理所有可能的环形排列情况。

Q: 为什么空间复杂度是O(1)？
A: 因为我们只使用了固定数量的变量，没有使用与输入规模相关的额外空间。

面试提示：解释清楚如何将环形问题转化为线性问题，并说明动态规划的状态转移过程，这能展示你对问题的深入理解。