leetcode：198. 打家劫舍（java 暴力搜索，记忆华搜索，dp）

系统管理员 2021-09-28 07:22 200阅读 0赞

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，**如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警**。

给定一个代表每个房屋存放金额的非负整数数组，计算你**在不触动警报装置的情况下，**能够偷窃到的最高金额。

**示例 1:**

输入: [1,2,3,1]
    输出: 4
    解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
         偷窃到的最高金额 = 1 + 3 = 4 。

**示例 2:**

输入: [2,7,9,3,1]
    输出: 12
    解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
         偷窃到的最高金额 = 2 + 9 + 1 = 12 。

第一种方法是暴力时间复杂度肯定超了

class Solution {
        public int rob(int[] nums) {
                return solve(nums.length - 1,nums);
        }
        public int solve(int index,int[] nums){
            if(index<0){
                return 0;
            }
            return Math.max(nums[index]+solve(index-2,nums),solve(index-1,nums));
        }
    }

第二种通过对暴力的记忆化处理通过

class Solution {
        public int rob(int[] nums) {
            int[] res=new int[nums.length];
            for (int i = 0; i <res.length ; i++) {
                res[i]=-1;
            }
            return solve(nums.length - 1,nums,res);
        }
        public int solve(int index,int[] nums,int[] res){
            if(index<0){
                return 0;
            }
            //通过比对以前是否计算过
            if(res[index]>=0){
                return res[index];
            }
            
            //把结果记录下来减少递归次数
            res[index] = Math.max(nums[index]+solve(index-2,nums,res),solve(index-1,nums,res));
            return res[index];
        }
    }

第三种是对记忆化搜索的自下而上的更改更像dp

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