LeetCode-198. 打家劫舍

男娘i 2024-03-25 20:51 49阅读 0赞

#### 目录 ####

*   *  暴力递归
     *  动态规划

题目来源  
[198. 打家劫舍][198.]

### 暴力递归 ###

class Solution {
        
        public int rob(int[] nums) {
        
            if(nums == null || nums.length==0){
        
                return 0;
            }
            return dfs(0,nums);
        }
    
        private int dfs(int i,int[] nums){
        
            //考虑要 i+2 所以要大于
            if(i >= nums.length){
        
                return 0;
            }
            //偷
            int stealy = nums[i]+dfs(i+2,nums);
            //不偷
            int stealn = dfs(i+1,nums);
            return Math.max(stealy,stealn);
        }
    }

![在这里插入图片描述][de2d6cd03f7b474e9324a89111eb4a89.png]

### 动态规划 ###

*  1.确定dp数组（dp table）以及下标的含义

dp\[i\]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp\[i\]。

*  2.确定递推公式

决定dp\[i\]的因素就是第i房间偷还是不偷。  
如果偷第i房间，那么dp\[i\] = dp\[i - 2\] + nums\[i\] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp\[i-2\] 加上第i房间偷到的钱。  
如果不偷第i房间，那么dp\[i\] = dp\[i - 1\]，即考 虑i-1房  
然后dp\[i\]取最大值，即**dp\[i\] = max(dp\[i - 2\] + nums\[i\], dp\[i - 1\]);**

*  3.dp数组如何初始化

从递推公式dp\[i\] = Math.max(dp\[i - 2\] + nums\[i\], dp\[i - 1\]);可以看出，递推公式的基础就是dp\[0\] 和 dp\[1\]

从dp\[i\]的定义上来讲，dp\[0\] 一定是 nums\[0\]，dp\[1\]就是nums\[0\]和nums\[1\]的最大值即：dp\[1\] = Math.max(nums\[0\], nums\[1\]);

int[] dp = new int[nums.length];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0],nums[1]);

**如果不取最大值，就会报错**  
![在这里插入图片描述][63f768d7e9aa459ea69860a56cc61c3d.png]  
![在这里插入图片描述][20a7e7dfa1cb4cdf91ba66dec6e5a5f2.png]

*  1.  确定遍历顺序

dp\[i\] 是根据dp\[i - 2\] 和 dp\[i - 1\] 推导出来的，那么一定是从前到后遍历！

for(int i = 2;i<nums.length;i++){
        
                dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
            }

*  5.举例推导dp数组

输入\[2,7,9,3,1\]为例  
![在这里插入图片描述][2113828c0d784ea69fe38b1904c143a0.png]  
代码

class Solution {
        
        public int rob(int[] nums) {
        
            if(nums.length == 0){
        
                return 0;
            }
            if (nums.length == 1) {
        
                return nums[0];
            }
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0],nums[1]);
            for(int i = 2;i<nums.length;i++){
        
                dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
            }
            return dp[nums.length-1];
        }
    }

![在这里插入图片描述][e49079013354405189936cb729b1289a.png]

[198.]: https://leetcode.cn/problems/house-robber/
[de2d6cd03f7b474e9324a89111eb4a89.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3becb3ae33b94a1892fe6b3f95545b6d.png
[63f768d7e9aa459ea69860a56cc61c3d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/09c94245d1894c459946fae02f549697.png
[20a7e7dfa1cb4cdf91ba66dec6e5a5f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/87e4c34f11214be6bbacad7f81e477fc.png
[2113828c0d784ea69fe38b1904c143a0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/93a1abc51fca4dd097b50a13b7bed625.png
[e49079013354405189936cb729b1289a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a20c741515804f81a56a5c47725b486c.png