打家劫舍(一)

题意

给定一个数字数组，不能选相邻的两个数，问选出的数的最大的和是多大

方法

深搜(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) {
        return dfs(nums,0);
    }
};

复杂度分析

时间复杂度: 最坏情况，相当于尝试了所有组合，所以总时间复杂度为$O(2^n)O(2^n)$

空间复杂度: 主要和递归深度相关，递归深度不超过数组长度，所以空间复杂度为$O(n)O(n)$

动态规划

分析

如果我们从左向右选数

那么一个位置是否可以选，仅仅与它左侧的值是否被选相关

定义状态$dp[i][\mathrm{是}\mathrm{否}\mathrm{选}\mathrm{则}]dp[i][是否选则]$表示从开头到第i个位置，且第i个位置的值是否被选的时的最大的和

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

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

样例

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

所以最后输出6，即可

代码

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 = 0;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); // 更新最大值
                }
            }
        }
        return max(dp[nums.size()][0],dp[nums.size()][1]); // 最后一个选和不选的最大的方案
    }
};

复杂度分析

空间复杂度: 主要是设计的状态的值的保存，所以空间复杂度为$O(n)O(n)$

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