LeetCode 198:House Robber

题意描述

给定一个非负整数数组，找出其中累加和的最大值，并且相邻元素不能进行累加。

测试用例

Input: [1,2,3,1]

Output: 4

Explanation: Total amount you can rob = 1 + 3 = 4.

Input: [2,7,9,3,1]

Output: 12

Explanation: Total amount you can rob = 2 + 9 + 1 = 12.

解题思路

一、思路一

使用动态规划

• 使用dp【i】表示数组【0，i-1】相隔累加和的最大值.

• 观察前几项

  • dp【0】= nums【0】，

  • dp【1】 = Math.max(nums【0】,nums【1】)，

  • dp【2】 = Math.max(nums【0】+nums【2】,nums【1】)，

  • dp【3】 = Math.max(nums【0】+nums【2】,nums【1】+nums【3】)，

  • dp【4】 = Math.max(nums【0】+nums【2】+nums【4】,nums【1】+nums【3】)

    ? = Math.max(dp【2】+nums【4】,dp【3】)

• 由上可以得出：dp【i】= Math.max(num【i】+dp【i-2】,dp【i-1】)

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

    public int rob(int[] nums) {
            int rob = 0;	//累加当前值的最大累加和
            int notrob = 0;	//不累加当前值的最大累加和
            for(int i=0;i