刷算法(15)-打家劫舍

198. 打家劫舍

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

解法

public int rob(int[] nums) {
    if (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];
}

心得

1. 要注意边界条件，考虑nums数组为空时返回0
2. 要自己分析动态规划方程:

   dp[n] = MAX( dp[n-1], dp[n-2] + num )

参考

• 画解算法：198. 打家劫舍