题目

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

解析

题目中有两点需要注意，一是不是偷连续两天的屋子，二是保证所偷屋子的总和最大。
这里逻辑到的算法是动态规划算法，即数组中不连续的值的最大值。
假设maxVal[i]为到达第i个房间的最大value，那么就有：
maxVal[i] = max(maxVal[i - 2] + nums[i], maxVal[i - 1])
该公式可以理解为：
到第i个房间的最大收益为，到第i-2个房间的最大收益与第i个房间的收益之和，与到第i-1个房间最大收益，这两者的最大值。
此题和上楼问题类似（LeetCode 70），即最后一步是由其上一步上一阶和上上步上两阶上来之和。
得出了该公式之后，代码的实现就简单了。

代码（C语言）

int max(int val1, int val2);
int rob(int* nums, int numsSize) {
    if (nums == NULL || numsSize == 0)
        return 0;
    
    if (numsSize == 1) {
        return nums[0];
    }
    
    int* maxValueArr = (int*)malloc(sizeof(int) * numsSize);
    
    maxValueArr[0] = nums[0];
    maxValueArr[1] = max(nums[0], nums[1]);
    
    for (int i = 2; i < numsSize; ++i) {
        maxValueArr[i] = max(maxValueArr[i - 2] + nums[i], maxValueArr[i - 1]);
    }
    
    int maxValue = maxValueArr[numsSize - 1];
    free(maxValueArr);
    
    return maxValue;
}

int max(int val1, int val2) {
    return val1 > val2 ? val1 : val2;
}