Leetcode 213. 打家劫舍 II(动态规划，递推)

问题描述：

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

Example

示例 1：
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。

题目链接：213. 打家劫舍 II (难度:中等)

思路

对于首尾的情况，一共可以分为4种

• 首尾都不偷；
• 偷首不偷尾；
• 偷尾不偷首；
• 首尾都偷；

显然由题目的描述可知，第 4 种情况会触发报警系统。因此我们需要排除第 4 种情况。另外，第 1 种情况，其实已经包含在第 2 种和第 3 种情况当中。因此我们只需要考虑第 2 种和第 3 种情况即可，可以采用两次dp，一次从0偷到n-1，一次从1偷到n，返回两次dp中的最大值即可。

动态规划三要素

1. dp定义：
   dp[i] = x：从第 i 间房开始偷，小偷所能得到的最大金额
2. 状态与状态转移方程：
   ①、第 i 间房不偷，则去第 i + 1 间房看看，dp[i] = dp[i+1]
   ②、第 i 间房偷，则去第 i + 2 间房看看，dp[i] = dp[i + 2] + nums[i];
   方程：dp[i] = max(dp[i + 1], dp[i + 2] + nums[i]);
3. 初态与终态
   初态：dp[n] = 0
   终态：dp1[0], dp2[1]
   其中，dp1[i]表示从0偷到n-1号房，dp2[i]表示从1偷到n号房

代码

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        int n = nums.size();
        if(n == 1) return nums[0];
        // 此处采用递推实现，dp1_i_1 表示 dp1[i-1]，dp1_i_2 表示 dp1[i-2]，以此类推
        int dp1_i = 0, dp1_i_1 = 0, dp1_i_2 = 0;
        int dp2_i = 0, dp2_i_1 = 0, dp2_i_2 = 0;
        for(int i = n - 1; i >= 1; --i){
            dp1_i = max(dp1_i_1, dp1_i_2 + nums[i]);
            dp1_i_2 = dp1_i_1;
            dp1_i_1 = dp1_i;
        }
        for(int j = n - 2;j >= 0;--j){
            dp2_i = max(dp2_i_1,dp2_i_2 + nums[j]);
            dp2_i_2 = dp2_i_1;
            dp2_i_1 = dp2_i;
        }
        return dp1_i > dp2_i ? dp1_i : dp2_i;
    }
};

执行结果： 0 ms, 7.9 MB