打家劫舍

198. 打家劫舍

解题思路

对于当前房间有两种选择，偷或不偷。如果选择偷，那么前一个房间就不能偷，如果不偷，那当前房间就相当于不存在，等价于面对前一个房间，而前一个房间的结果已经计算出来了，因此只需要比较出偷或不偷两种方式的较大值即为面对当前房间的结果。

首先利用一个数组用来存储已经计算出来房间的结果，将数组长度设置为 nums.length+1，是为了方便之后的计算。开始初始化，将dp[0]设置为0，显然第0号房间不存在，所以偷不偷都是0，dp[1]设置为1，此时偷肯定比不偷获利更大，初始化完成。从第二个房间开始循环，如果不偷当前房间，获利就是前一个房间的结果，即dp[i]，如果偷当前房间，获利就是当前房间的值加上倒数第二个的值，即nums[i] + dp[i-1]，取它们的较大值为结果。数组中最后一个值即为最大获利。

代码

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

总结

动态规划是空间换时间的算法，当然很多时候可以优化空间占用，本题中，其实只需记录当前元素之前的两个元素的值即可，只是需要在每次循环的末尾将元素的值进行替换即可。