目录

• • 暴力递归
  • 动态规划

题目来源
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);}
}

动态规划

• 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]);

如果不取最大值，就会报错

• 4. 确定遍历顺序

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

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

• 5.举例推导dp数组

输入[2,7,9,3,1]为例

代码

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;idp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);}return dp[nums.length-1];}
}