198. 打家劫舍

1、题目描述

 2、题目分析

        本题目是【动态规划】类型比较经典的题目，之前对【买股票问题】【打家劫舍问题】专门进行过专题分析，专题分析会把同类型的题目进行汇总并且对比，比本次单题目书写要更全面些。建议去看下我之前写的，该类题目专题的博文，对应的链接如下：

       算法分享系列No.7--(大厂面试实际问题) 股票买卖系列 & 打家劫舍问题

因此此类题目主要是找到递推方程。递推思路如下：

 根据上述递推逻辑，使用辅助空间dp的代码实现如下：

class Solution {
    public int rob(int[] nums) {
        //初始情况
        int n = nums.length;
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        
        //动态规划，辅助空间dp
        int[] dp = new int[n];
        //进行初始化
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i = 2; i < n; i++){
          //动态规划转移方程式
          dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[n-1];
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。

空间复杂度：O(n)。使用辅助空间dp数组，记录每个元素暂存结果。

        在上面基础上进行空间优化，因为发现，这个数值，就跟【前两间】房屋的金额有关，因此无需专门使用dp辅助空间进行记录，可以变更成变量即可，这样空间复杂度从原数组O(n)降低到有限个变量元素，空间复杂度下降到O(1)。

此时，【优化空间复杂度】的写法如下：

class Solution {
    public int rob(int[] nums) {
        //初始情况
        int n = nums.length;
        if(n == 0) return 0;
        if(n == 1) return nums[0];

        int one = nums[0];
        int second = Math.max(nums[0],nums[1]);
        for(int i =2; i< n; i++){
            //滚动计算
            int temp = second;
            second = Math.max(one+nums[i], second);
            one = temp;
        }
        return second;
   }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。

空间复杂度：O(1)。使用滚动数组，可以只存储前两间房屋的最高总金额，而不需要存储整个数组的结果，因此空间复杂度是 O(1)。