打家劫舍(二)

题意

给定一个数字数组，它们构成环，不能选相邻的两个数，问选的数的最大的和是多大

方法

深搜(TLE)

分析

我们递归搜索，每次有可选的起始位置。

如果选定这个位置，那么下一层递归，则可选位置从当前位置+2开始

如果不选这个位置，那么下一层递归，可选位置从当前位置+1开始

在递归过程中记录选择的和

最后输出和中的最大值

这样的问题在于，没有处理首个位置和末尾的位置相邻的情况

考虑对第一个位置单独处理，分别讨论选和不选

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

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

代码

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) // 不选当前，下一个可选位置就是idx+1
        );
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    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][true\mathrm{/}false]dp[i][true/false]$表示从开头到第i个位置，且第i个位置的值是否被选的时的最大的和

这样每个状态仅依赖于上一个位置的状态

其中如果当前和上一个都是可选的状态则不更新

注意到还要处理首尾

和上面一样，分别讨论第一个选择的情况

样例

以样例数据[1,2,3,4]为例

所以最后输出结果即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    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)$

时间复杂度: 每个状态的计算都是常数代价，所以总时间复杂度为$O(n)O(n)$