3.打家劫舍

$dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])$

• 2.17
  • 秒了，但是 dp【1】的初始化错了，可以选择偷第一个也可以偷第二个

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

• 2.4
  • 依旧根据需要初始化 dp 数组时，添加前置判断条件

class Solution {
    public int rob(int[] nums) {
        if(nums.length==1) return nums[0];
        if(nums.length==2) return Math.max(nums[0],nums[1]);
        int[] dp = new int[nums.length];
        dp[0] =nums[0];
        dp[1] = Math.max(nums[1],nums[0]);
        // if(nums.length>=2) return Math.max(dp[0],dp[1])错误，直接就截流返回了
 
        for(int i=2;i<nums.length;i++){
            dp[i] = Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[nums.length-1];
    }

12.4

• 第二种更易懂(不同于1,4题,这里传入的是数组)
  • dp[i] 就是 nums[i] 这个位置的最优解
  • 这里其实只要记住定义dp长度(比如n)时,for循环走完长度i<n,然后返回dp[n-1]也就是末尾
• 第一种
  • nums[i-1]才是当前房子(第i个房子)

class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length+1];
        if(nums.length==0) return 0;
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i=2;i<nums.length+1;i++){
	        //nums[i-1]才是当前房子(第i个房子)
            dp[i] = Math.max(dp[i-2]+nums[i-1],dp[i-1]);
        }
        return dp[nums.length];
    }
}

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n==1) return nums[0];
        if(n==2) return Math.max(nums[0],nums[1]);
        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-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
}