打家劫舍

原题链接

使用的方法

动态规划

解题思路

对于每一间房屋，我们有两个选择：偷或者不偷。

• 如果我们偷了当前房屋，那么就不能偷前一间房屋；
• 如果我们不偷当前房屋，那么可以考虑偷前一间房屋。
• 因此，我们可以用动态规划来解决这个问题。

代码实现

class Solution {
    public int rob(int[] nums) {

        // 边界情况：没有房屋
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 边界情况：只有一间房屋
        if (nums.length == 1) {
            return nums[0];
        }

        int prev2 = nums[0]; // 代表dp[i-2]
        int prev1 = Math.max(nums[0],nums[1]); // 代表dp[i-1]

        for(int i=2; i<nums.length ; i++){
            int cur = Math.max(prev1,prev2 + nums[i]);

            prev2 = prev1;
            prev1 = cur;
        }

        return prev1;
    }
}