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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int rob (int[] nums) {
        // write code here
        /*这种做法不对，且超时
        int res=0;
        for(int i=0;i<nums.length;i++)//从第i家开始偷
        {
            int tmp=0;
            //跳着偷，但这样其实不对，因为有时候会为了偷取更多的钱，或许可能会连续放弃两家不偷
            for(int j=i+2;j<nums.length;j+=2)
            {
                tmp+=nums[j];
            }
            tmp+=nums[i];
            res=Math.max(res,tmp);
        }
        return res;
        */
	  //dp[i]表示：偷长度为i的数组，最多能偷多少钱
	  //dp[1]=nums[0]
	  //对于每一家，可以偷或者不偷，不偷的话，dp[i]=dp[i-1];偷的话：dp[i]=dp[i-2]+nums[i-1]
        int[] dp = new int[nums.length+1];
        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];

    }
}