联结

dp[i]为0-i数组中不相邻数据的最大值，对于i个数据可以取也可以不取，若取的话则值为 dp[i-2]+nums[i],若不取的话则dp[i-1]则状态转移方程dp[i]=Max(dp[i-1],dp[i-2]+nums[i])；初始值dp[0]=nums[0],dp[1]=Max(nums[0],nums[1])

package BDyNamicProgramming;

/**
 * @Author Zhou  jian
 * @Date 2020 ${month}  2020/4/21 0021  17:16
 */
public class Problem1716 {

    /**
     * dp[i]数组0-中最大和（数据不相邻）
     * dp[0]=nums[0],dp[1]=max(nums[0].nums[1]）
     * dp[i]=max(dp[i-1],dp[i-2]+nums[i])
     * @param nums
     * @return
     */
    public int massage(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<nums.length;i++){
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }
}

原题链接: Maximum sum such that no two elements are adjacent

题目
给定一个只含正数的数组，找到数组满足条件的元素的最大和，条件是：组成最大和的所有元素不能相邻，比如数组 [3,2,7,10] 返回 13（3+10），数组 [3,2,5,10,7] 返回（3+5+7）

解题思路:
遍历array 中的所有元素，设置两个变量：
excl: 不包含前一个元素的最大和
incl: 包含前一个元素的最大和

更新当前元素的 excl 和 incl：
不包含当前元素的最大和 excl = max(incl’， excl’)
包含当前元素的最大和 incl = excl’+current (元素不能相邻)

arr[] = {5,  5, 10, 40, 50, 35}
1) arr[0] = 5
   incl = 5 
   excl = 0
2) arr[1] = 5
   incl =  (excl + arr[1])  = 5
   excl =  max(5, 0) = 5
3) arr[2] = 10
   incl =  (excl + arr[2])  = 15
   excl =  max(5, 5) = 5
4) arr[3] = 40
   incl =  (excl + arr[3])  = 45
   excl =  max(5, 15) = 15
5) arr[4] = 50
   incl =  (excl + arr[4])  = 65
   excl =  max(15, 45) = 45
5) arr[5] = 35
   incl =  (excl + arr[5])  = 80
   excl =  max(45, 65) = 65

answer is max(incl, excl) =  80

代码

#include <iostream>

using namespace std;

int maxSum(int *arr, int size)
{
        if(size<=0)
                return 0;
        else if(size ==1)
                return arr[0];

        int excl = 0, incl = arr[0];
        int excl_new;
        for(int i = 1; i<size; ++i)
        {
                excl_new = (excl>incl)?excl:incl;
                incl = excl + arr[i];
                excl = excl_new;
        }
        return (incl>excl)?incl:excl;
}

int main()
{
        int array[] = {5,5,10,40,50,35};
        cout<<maxSum(array, 6)<<endl;
}

题目内容

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400

标签：动态规划

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法效率

解法一（动态规划）：

【思路】 简单思考，得到如下思路：

如果想取得最大值，那数组中每两个相邻的取值之间，只可能间隔1个数或2个数，开头有两种选择，从第一个数开始取和从第二个数开始取。

所以如果在取得第i个数，此时其最大值只能来自：取得第i-2个数的最大值再加第i个数、取得第i-3个数的最大值再加第i个数。

又有当i=0时，最大值为nums[0]；当i=1时，最大值为nums[1]；当i=2时，最大值为nums[0]+nums[2]；当i>=3时，可使用上一段的方法计算。

最终数列取得的最大值为取得nums[-1]和取得nums[-2]的两个最大值中更大的那一个。

由此得出如下初步的逻辑（这要真能运行也会慢死）：

def rob(self, nums: List[int]) -> int:
    def helper(i):
        if i == 0:
            return nums[0]
        elif i == 1:
            return nums[1]
        elif i == 2:
            return nums[0] + nums[2]
        else:
            return max(helper(i - 2), helper(i - 3)) + nums[i]

    size = len(nums)
    if size == 0:
        return 0
    elif size == 1:
        return nums[0]
    else:
        return max(helper(size - 1), helper(size - 2))

解法二（滚动数组）：

【思路】对以上算法进行优化，改用滚动数组的方法，将其空间复杂度优化为O(1)，时间复杂度优化为O(n)。

def rob(self, nums: List[int]) -> int:
    size = len(nums)
    if size == 0:
        return 0
    elif size == 1:
        return nums[0]
    elif size == 2:
        return max(nums[0], nums[1])
    else:
        sum_1 = nums[0]  # 取得第i-3个数的最大值
        sum_2 = nums[1]  # 取得第i-2个数的最大值
        sum_3 = nums[0] + nums[2]  # 取得第i-1个数的最大值
        for i in range(3, size):
            n = nums[i]
            sum_4 = max(sum_1 + n, sum_2 + n)  # 取得第i个数的最大值
            sum_1 = sum_2
            sum_2 = sum_3
            sum_3 = sum_4
        return max(sum_2, sum_3)

解法三（更简单的思路）：

【思路】此时，我们还有一个更简单的思路：

我们可以不再考虑取得某个数时的最大值，改为考虑截止到某个数的最大值。

此时，如果我们取得的某两个数（第i个数和第i+3个数）之间间隔了2个数，那么说明截止到第i个数的最大值和截止到第i+1个数的最大值是相同的。

因此，当我们改为考虑截止到某个数的最大值时，截止到第i个数的最大值只可能来自：截止到第i-2个数的最大值加第i个数、截止到第i-1个数的最大值。

由此如下的逻辑：

def rob(self, nums: List[int]) -> int:
    size = len(nums)
    if size == 0:
        return 0
    elif size == 1:
        return nums[0]
    else:
        sum_1 = nums[0]
        sum_2 = max(nums[0], nums[1])
        for i in range(2, size):
            sum_3 = max(sum_1 + nums[i], sum_2)
            sum_1 = sum_2
            sum_2 = sum_3
        return max(sum_1, sum_2)