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

打家劫舍(一)

题目描述

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

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

方法一：递归法

解题思路

对于本题目的求解，使用递归搜索的方法进行，对于每次选择的位置，如果选定当前位置，那么下次递归可从当前位置往后移动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)
        );
    }
    int rob(vector<int>& nums) {
        return dfs(nums,0);
    }
};

复杂度分析

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

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

方法二：动态规划的方法

解题思路

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

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

解题代码

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 = 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)$。

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