题解 | #打家劫舍(一)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    //动态规划的解法
    //定义一个同样大小的dp数组，其含义位dp[i]的含义为从第0家偷到第i家时能偷到的最大财产为dp[i]这么大
    //假设当前来到某一家时，小偷可以选择偷这一家也可以选择不偷，如果选择偷，那么dp[i]=dp[i-2]+arr[i],
    //如果不偷这一家那么dp[i]=dp[i-1].
    //dp数组的初始化为d[0]=arr[0],dp[1]=max{arr[0],arr[1]};
    public int rob (int[] nums) {
        // write code here
        if(nums.length<=0)
            return 0;
        //考虑到nums数组的特殊情况，如果nums数组只有一个值，那直接返回这个值即可
        if(nums.length==1)
            return nums[0];
        int []dp=new int[nums.length];//申请一个dp数组
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);//初始化完成
        for(int i=2;i<dp.length;i++){
            //当前来到第i家有两种选择，偷或者不偷,取这两个决策下的最大收益
            dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[dp.length-1];//返回最大值
    }
}