来自leecode 的题目“打家劫舍”，题目大概意思是这样：在一条街道上有一排房屋，每家屋内有一定数量的现金，而相邻的屋子装有连通的防盗系统，如果相邻的两屋子被偷，系统就会报警。如果你是个聪明的小偷，在不触发系统报警的情况下，你最大能够偷多少现金。

比如用一个数组 nums = [2,3,4,2] 表示，有四个屋子，每个里面分别现金是2，3，4，2。那么偷1号屋（现金2）和3号屋（现金4），最优解是可以偷到6。

该题简化意思是：不能连续地取数组内数字，取到的最大数字和为多少。

该问题是动态规划的一个比较好的例子。动态规范的问题思想是把原问题分解为子问题，计算子问题的解后再推算原问题，而原问题和子问题有相似之处，在递归计算子问题时候加上记忆化存储，省去大量可能重复的子问题计算。

也就是：动态规划本质=递归求解 + 记忆化存储。

题解分析：由于不能连续偷两个屋子，从最后一个屋子n来看，最大可偷值不外乎两种情况：要么偷n号屋子；要么不偷。

这里先定义n个屋子最大能偷的函数方程为：F(n)。

1）如果偷屋n，那么屋子n-1 是不能偷，剩下1到n-2个屋子能偷的最优解，加上nums[n] 即是该情况的最优解，也就是 nums[n] + F(n-2)

2）如果不偷n，那么1 到n-1 号屋子最大能偷的结果为 该情况的最优解。也就是 F(n-1)。

综上面1）和2）情况，最优解方程 F(n) = max(F(n-2) + nums[n], F(n-1))。

再补上n<=2的情况，则得：

// 为方便表示，伪代码下标用 1 表示第一家，2 表示第二家，类推。
F(n=1) = nums[1] // 只有一家，最大为直接偷即可
F(n=2) = max(nums[1],nums[2]) 
F(n>2) = max(F(n-2) + nums[n], F(n-1))

一、算法版本A

根据上面伪代码整理出 C 代码为：

int max(int a, int b)
{
    return a > b ? a:b;
}

int rob(int* nums, int numsSize)
{
    if (numsSize == 1) { return nums[0]; }
    if (numsSize == 2) { return max(nums[0],nums[1]); }

    return max(nums[numsSize - 1] + rob(nums, numsSize-2), rob(nums, numsSize-1));
}

二、算法版本B

上面主要是用了递归，没有对子问题的求解进行存储，所以在计算较大的n 时候会出现大量的重复计算其子问题，直接提交会超时。同时也不符合动态规划的“记忆化存储”。

对算法进行下调整，增加下cache：

int _rob(int* nums, int numsSize, int *cache)
{
    if (cache[numsSize - 1] != -1) { 
        return cache[numsSize - 1]; 
    }

    int ans;
    if (numsSize == 1) { 
        ans = nums[0];
    }
    else if (numsSize == 2) { 
        ans = max(nums[0],nums[1]); 
    }
    else {
        ans = max(nums[numsSize - 1] + _rob(nums, numsSize-2, cache), _rob(nums, numsSize-1, cache));
    }

    cache[numsSize - 1] = ans;
    return ans;
}

int rob(int* nums, int numsSize)
{
    int *cache = (int *)malloc(sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; i++) {
        cache[i] = -1;
    }

    int ans = _rob(nums, numsSize, cache);
    free(cache);

    return ans;
}

上面算法是从n 往1 递减来求解的，同时也额外用了O(n)空间作为cache。该问题如果从1 向n 来算，空间是可以用到O(1)的，看下面解法。

三、算法版本C

回头看上面的递推公式：

F(n=1) = nums[1] 
F(n=2) = max(nums[1],nums[2]) 
F(n=3) = max(F(1) + nums[3], F(2))
F(n=4) = max(F(2) + nums[4], F(3))
.
.
.
F(n) = max(F(n-2) + nums[n], F(n-1))

在算F(n) 的时候，只需要知道 F(n-1)和F(n-2) 就可，其他的就已经不需要了。所以从小往大递推，缓存空间是可以复用的。代码：

int rob(int* nums, int numsSize){
    if (numsSize == 1) return nums[0];
    if (numsSize == 2) return max(nums[0],nums[1]);

    int t1 = nums[0];              // n - 2
    int t2 = max(nums[0],nums[1]); // n - 1
    int ans = 0;
    for (int i = 3; i <= numsSize; i++) {
        ans = max(nums[i-1] + t1, t2);
        t1 = t2;
        t2 = ans;
    }

    return ans;
}

至此，代码简短，算法时间复杂度O(n),空间复杂度O(1)了。

（全文完）

（欢迎转载本站文章，但请注明作者和出处 云域 – Yuccn ）