初始理解问题
首先，我们需要明确题目在问什么。题目“House Robber”描述的是一个强盗在一排房屋前，每个房屋都有一定数量的钱。强盗不能连续抢劫两个相邻的房屋，否则会触发警报。目标是抢劫到最多的钱。
动态规划的思路
这个问题可以使用动态规划（Dynamic Programming, DP）来解决。动态规划是一种分阶段解决问题的方法，通常用于具有重叠子问题和最优子结构性质的问题。在这里，我们需要找到在不能连续抢劫两个相邻房屋的情况下，能够获得的最大金额。
DP数组的定义
在给定的代码中，dp是一个数组，其中dp[i]表示到达第i个房屋时能够抢劫到的最大金额。这里的“到达”并不意味着一定要抢劫第i个房屋，而是表示在前i个房屋中，按照规则能够获得的最大金额。
DP数组的初始化
-
基本情况1：没有房屋（
nums.empty()）
如果没有房屋，那么能抢劫的最大金额自然是0。if (nums.empty()) {return 0; } -
基本情况2：只有一个房屋（
size == 1）
如果只有一个房屋，那么只能抢劫这个房屋，最大金额就是nums[0]。if (size == 1) {return nums[0]; } -
基本情况3：两个房屋
如果有两个房屋，强盗不能同时抢劫这两个房屋，所以选择金额较大的那个。dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]);
DP递推关系
对于第i个房屋（i >= 2），有两个选择：
-
抢劫第
i个房屋：
如果抢劫第i个房屋，那么不能抢劫第i-1个房屋。因此，最大金额为dp[i-2] + nums[i]（即前i-2个房屋的最大金额加上当前房屋的金额）。 -
不抢劫第
i个房屋：
如果不抢劫第i个房屋，那么最大金额与前i-1个房屋的最大金额相同，即dp[i-1]。
为了最大化总金额，我们选择这两种情况中的较大值：
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
示例解析
假设nums = [2, 7, 9, 3, 1]：
-
初始化：
dp[0] = 2（只有第一个房屋）dp[1] = max(2, 7) = 7（第一或第二个房屋，选较大的）
-
计算
dp[2]：- 抢劫第三个房屋：
dp[0] + nums[2] = 2 + 9 = 11 - 不抢劫第三个房屋：
dp[1] = 7 dp[2] = max(11, 7) = 11
- 抢劫第三个房屋：
-
计算
dp[3]：- 抢劫第四个房屋：
dp[1] + nums[3] = 7 + 3 = 10 - 不抢劫第四个房屋：
dp[2] = 11 dp[3] = max(10, 11) = 11
- 抢劫第四个房屋：
-
计算
dp[4]：- 抢劫第五个房屋：
dp[2] + nums[4] = 11 + 1 = 12 - 不抢劫第五个房屋：
dp[3] = 11 dp[4] = max(12, 11) = 12
- 抢劫第五个房屋：
最终，dp = [2, 7, 11, 11, 12]，返回dp[4] = 12。
为什么这样定义dp[i]
dp[i]表示“考虑前i+1个房屋（因为索引从0开始）时能够获得的最大金额”。这个定义允许我们通过子问题的解来构建更大问题的解，这是动态规划的核心思想。具体来说：
dp[i]依赖于dp[i-1]和dp[i-2]，这表示当前的最大金额取决于前一个房屋和前两个房屋的最大金额。- 通过这种方式，我们可以确保不连续抢劫两个相邻的房屋，因为如果抢劫了
i，就会跳过i-1，使用dp[i-2]。
时间复杂度和空间复杂度
- 时间复杂度：O(n)，因为我们只需要遍历一次
nums数组。 - 空间复杂度：O(n)，因为我们使用了一个大小为
n的dp数组。实际上，可以优化到O(1)空间，因为dp[i]只依赖于dp[i-1]和dp[i-2]，可以用两个变量代替整个数组。
可能的优化
可以优化空间复杂度，只保留前两个状态：
int rob(vector<int>& nums) {int prev = 0, curr = 0;for (int num : nums) {int temp = curr;curr = max(prev + num, curr);prev = temp;}return curr;
}
这样，空间复杂度降为O(1)。
总结
dp[i]表示“在前i+1个房屋中，按照规则能够抢劫到的最大金额”。- 通过比较“抢劫当前房屋”和“不抢劫当前房屋”两种情况的最大值来更新
dp[i]。 - 初始化
dp[0]和dp[1]作为基础情况。 - 最终结果是
dp[n-1]，其中n是房屋的数量。
这种方法确保了我们在每一步都做出最优的选择，从而在全局上得到最大的抢劫金额。
：Cookie与会话)
)
技术)
