环形房屋抢劫问题：动态规划解题逻辑与技巧

问题背景

这是一个经典的动态规划变种问题。假设有一排环形排列的房屋，每间屋内有一定金额。如果偷窃相邻的两间房屋就会触发警报。我们需要计算在不触发警报的情况下能够偷窃到的最高金额。

解题策略

由于房屋是环形的，第一间和最后一间也是相邻的，这意味着它们不能同时被偷。我们可以将这个问题拆解为两个线性子问题：

1. 不偷第一间房屋，只考虑从第二间到最后一间。
2. 不偷最后一间房屋，只考虑从第一间到倒数第二间。

最终结果取这两个子问题的最大值。这样就把环形约束转化为了标准的线性打家劫舍问题。

代码实现

我们先写一个辅助函数来处理线性排列的情况，主函数则负责调用两次辅助函数并比较结果。

#include <stdio.h>

// 处理线性排列的房屋
int robLinear(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;
}

// 处理环形排列
int rob(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    if (numsSize == 1) return nums[0];
    
    // 情况一：不偷最后一间（范围 [0, numsSize-1)）
    int option1 = robLinear(nums, 0, numsSize - 1);
    // 情况二：不偷第一间（范围 [1, numsSize)）
    int option2 = robLinear(nums, 1, numsSize);
    
    return (option1 > option2) ? option1 : option2;
}

  {
     nums1[] = {, , };
    (, rob(nums1, )); 
    
     nums2[] = {, , , };
    (, rob(nums2, )); 
    
     nums3[] = {, , };
    (, rob(nums3, )); 
    
     ;
}