LeetCode 213 打家劫舍II

本文主要是介绍LeetCode 213 打家劫舍II，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接：LeetCode 213 打家劫舍II

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

题解：
设\(dp[i]\)表示在下标范围\([start,i]\)内可以偷窃到的最高总金额，状态转移方程：

由于房屋围成一圈，所以分别取\((start,end)=(0,n−2)\)和\((start,end)=(1,n−1)\)进行计算，取两个\(dp[end]\)中的最大值，即可得到最终结果。
考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组。

class Solution {
public:
    int solve(vector<int>& nums, int start, int len) {
        int p = nums[start], q = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i < len; ++i) {
            int temp = q;
            q = max(p + nums[i], q);
            p = temp;
        }
        return q;
    }

    int rob(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0];
        } else if (nums.size() == 2) {
            return max(nums[0], nums[1]);
        } else {
            return max(solve(nums, 0, nums.size() - 1), solve(nums, 1, nums.size()));
        }
    }
};

这篇关于LeetCode 213 打家劫舍II的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！