题解 | #打家劫舍(二)#

打家劫舍(二)

题目描述

你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。

给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

方法一：递归法

解题思路

对于本题目的求解，使用递归搜索的方法进行，对于每次选择的位置，如果选定当前位置，那么下次递归可从当前位置往后移动2个开始，如果不选择当前位置，那么下次递归可从当前位置往后移动1个开始。在递归过程中记录最大值，最后输出即可。但此时没有考虑首个位置和末尾位置相邻的情况，对于第一个位置，我们分两种情况进行讨论：

1、如果第一个位置选了，那么最后一个位置不选，第二个位置不能选。

2、如果第一个位置不选，那么从第二个位置开始操作。

解题代码

class Solution {
public:
    // 数组，可选的起始位置，总和
    int dfs(vector<int>& nums,int idx,int sum = 0)
    {
        if(idx >= nums.size())
        {
            return sum;
        }
        return max(
            dfs(nums,idx+2,sum+nums[idx]),dfs(nums,idx+1,sum));
    }
    int rob(vector<int>& nums) 
    {
        int ans = dfs(nums,1); // 第一个位置不选, 对剩余部分递归
        int first = nums[0];// 第一个位置选，但是最后一个位置不选
        nums.pop_back();
        return max(ans,dfs(nums,2,first));
    }
};

复杂度分析

时间复杂度：最坏情况为尝试了所有的组合，因此时间复杂度为$O(2^n)O(2^n)$。

空间复杂度：使用递归，且深度不超过数组长度，因此空间复杂度为$O(n)O(n)$

方法二：动态规划的方法

解题思路

本题还可以使用动态规划的方法进行解决，dp[i][j]表示从开头到第i个位置，且第i个位置是否被选择时的最大的和。同时，有状态转移方程：

$dp[i+1][j]=max(dp[i+1][j],+dp[i][p]+nums[i]\ast j)dp[i+1][j]\; =\; max(dp[i+1][j],\; +\; dp[i][p]+nums[i]*j)$

同时还需要考虑第一个位置选择或者不选择的情况，同方法一。

解题代码

class Solution {
public:
    int rob(vector<int>& nums)
    {
        vector<vector<int> > dp = vector<vector<int> >(nums.size()+1,vector<int>(2,0));
        // 第一个不选，跳过第一个
        for(int i = 1;i<nums.size();i++)
        {
            for(int p = 0;p<2;p++)
            { // 上一个是否选
                for(int q=0;q<2;q++)
                { // 当前是否选
                    if(p&q)continue; // 不能同时选
                    dp[i+1][q] = max(dp[i+1][q],dp[i][p] + nums[i] * q); // 更新最大值
                }
            }
        }
        int ans = max(dp[nums.size()][0],dp[nums.size()][1]);
        // 第一个要选择, 则第二个和最后一个不能选
        nums.pop_back();
        dp = vector<vector<int> >(nums.size()+1,vector<int>(2,0));
        for(int i = 2;i<nums.size();i++)
        {
            for(int p = 0;p<2;p++)
            { // 上一个是否选
                for(int q=0;q<2;q++)
                { // 当前是否选
                    if(p&q)continue; // 不能同时选
                    dp[i+1][q] = max(dp[i+1][q],dp[i][p] + nums[i] * q); // 更新最大值
                }
            }
        }
        ans = max(ans,nums[0] + max(dp[nums.size()][0],dp[nums.size()][1]));
        return ans;//返回结果
    }
};

复杂度分析

时间复杂度：一层循环，因此时间复杂度为$O(n)O(n)$。

空间复杂度：使用dp数组，因此空间复杂度为$O(n)O(n)$，其中n为nums的大小。