LeetCode 198. 打家劫舍 Java

这种求什么最大钱数的问题，先想到动态规划或者贪心算法。
动态规划的思路是，先判断只有一间房子的时候，那么就偷这家。有两间房，偷钱多的。
有k间房，如果偷第k间房，则k-1不能偷，最大钱数为：前k-2间房的最大钱数+k。
如果不偷第k间房，最大钱数为：前k-1间房的最大钱数。
最后处理一下数组为空的情况。

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