leetcode198.打家劫舍I(java)：动态规划

题目

思路：动态规划

1. 状态：dp[i][0]表示不偷窃第i号房屋获得的最大金额，dp[i][1]表示盗窃第i号房屋获得的最大金额。
2. 状态转移方程：如果第i号不偷窃，那第i-1号是否偷窃无所谓，dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1])
   如果要偷窃第i号，那第i-1号不能偷窃，dp[i][1] = dp[i-1][0]+nums[i]
3. 初始化：dp[0][0]=0,dp[0][1]=nums[0]
4. 输出：return Math.max(dp[nums.length-1][0],dp[nums.length-1][1])

class Solution {
    public int rob(int[] nums) {
        //不要忘记这个判断
        if(nums == null||nums.length == 0){
            return 0;
        }
        int dp[][] = new int[nums.length][2];
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for(int i = 1;i < nums.length;i++){
            
                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);
                dp[i][1] = dp[i-1][0]+nums[i];
            
        }
        return Math.max(dp[nums.length - 1][0],dp[nums.length - 1][1]);
    }
}

时间复杂度：O(N)
空间复杂度：O(N)

改进：一维动态规划

1. 状态dp[i]表示到第i-1号房屋的最大偷窃金额。
2. 初始化：dp[0] = 0;dp[1]=nums[0]
3. 状态转移：第i号房屋的最大偷窃金额为偷窃第i-1家的最大金额和偷窃第i-2家和当前家的最大金额的最大值dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1)
4. 输出：dp[nums.length];

具体代码

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

另一种写法

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