讨论/《动态规划精讲(一)》 - 打家劫舍 II/
《动态规划精讲(一)》 - 打家劫舍 II
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n==1){
            return nums[0];
        }else if(n==2){
            return Math.max(nums[0],nums[1]);
        }
        int[] dp = new int[n-1]; //从0~n-2位置 不必考虑首尾状态
        int[] dp2 = new int[n]; //从1~n-1位置 不必考虑首尾状态

        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i =2;i<n-1;i++){
            dp[i] = Math.max(dp[i-2] + nums[i],dp[i-1]);
        }

        dp2[1] = nums[1];
        dp2[2] = Math.max(nums[1],nums[2]);

        for(int i=3;i<n;i++){
            dp2[i] = Math.max(dp2[i-2] + nums[i],dp2[i-1]);
        }

        return Math.max(dp[n-2],dp2[n-1]); //返回不可以偷最后一家、不可以偷第一家中2者情况的最大值
    }
}
1
展开全部 8 讨论