讨论/《初级算法》 - 打家劫舍/
《初级算法》 - 打家劫舍

image.png

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

    }

优化:
image.png

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


    }
展开全部 24 讨论