（力扣）198. 打家劫舍

题目

解题结果

解题思路：动态规划

题中提到“最高金额”，即求最优解代价。贪心策略和动态规划都可用于求解最优解问题。此问题是动态规划问题。

1. 定义最优解代价，题目已给出：“盗取金额总数”，dp[i]表示前i个房屋可获取的金额。
2. 定义最优解结构

• 如果dp[i-1]不包括最末尾房屋,则直接加上第i个房屋的金额（nums[i-1]），dp[i] = dp[i-1] + nums[i-1];
• 否则 dp[i] = Math.max(dp[i-2]+nums[i-1],dp[i-1]);

3. 递归求解最优解

注意初始化时要考虑dp[0],dp[1]等数组越界问题

解题代码

class Solution {
     //动态规划
    public int rob(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len+1];
        dp[0] = 0;
        if(len == 0){
            return dp[0];
        }
        dp[1] = nums[0];
        if(len == 1){
            return dp[1];
        }
        dp[2] = Math.max(nums[0],nums[1]);
        for(int i = 3;i<=len;i++){
            //需要判断当前已“打劫”的是否有末尾住户i
            if(dp[i-2] == dp[i-1]){
                //不包括末尾元素
                dp[i] = dp[i-1] + nums[i-1];
            }
            if(dp[i-2] < dp[i-1]){
                //包括了末尾元素
                dp[i] = Math.max(dp[i-2]+nums[i-1],dp[i-1]);
            }
        }
        return dp[len];
    }
}