打家劫舍问题(1)

打家劫舍问题(1)

来自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

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注