漫画算法：女友不给零花钱，我只能去「打家劫舍」！-技术圈

凌晨两点

接下来是二狗打家劫舍的思路

第1间：可以得1w。

前2间：只能在第1间和第2间中做选择（因为同一晚上进相邻的两个房间会报警），为了抢更多，傻子都知道抢第2间，这里面可是有2w呢！

前3间：有2种选择方式，第1间和第3间，或者仅选第2间。而选择第1间和第3间可以抢最多，是4w。

前4间：此时有3种选择方式，即第1间和第3间，第2间和第4间，第1间和第4间。选择第1间和第3间可以抢最多，是4w。

因此，最多可以抢4w。

在这里，我们用H_i表示第i+1间房的金额，M_i表示前i+1间房时获取的最大金额（i = 0,1,2....）。

第1间：M₀ = H₀ = 2

前2间：M₁ = max(M₀, H₁)= 7

前3间：M₂= max(M₁, M₀+H₂) = 11

前4间：M₃ = max(M₂, M₁+H₃) = 11

前5间：M₄ = max(M₃, M₂+H₄) = 12

以此类推，我们就可以得出有N间房时获得的最大金额。

代码实现：

int rob(int* nums, int numsSize){
        if (numsSize == 0) {
            return 0;
        }
        // 只有一间房时
        if (numsSize == 1) {
            return nums[0];
        }

        int first = nums[0];
        int second = nums[0] >= nums[1] ? nums[0] : nums[1];

        int dp = second, i;
        for (i = 2; i < numsSize; i++) {
            dp = first + nums[i] >= second ? first + nums[i] : second;
            first = second;
            second = dp;
        }

        return dp;
}

温馨提示

脑袋瓜虽好，可不要「误入歧途」喔！

- END -

读者福利

《程序员内功修炼》第二版强势来袭，汇总了高质量的算法、计算机基础文章并且每一篇文章，要嘛是漫画讲解，要嘛是对话讲解，一步步引导，要嘛是图形并茂，如果你想学习算法，学习计算机基础，那么我决定这份 PDF，一定会让你有所帮助。当然，如果一是一位有那么点迷茫的在校生，相信我的个人经历，可以给你打一份鸡血，让你更好着去寻找自己的目标。

文章整体目录

如何获取

很简单，在我的微信公众号 帅地玩编程 回复 程序员内功修炼 即可获取《程序员内功修炼》第一版和第二版的 PDF。

推荐，推荐一个 GitHub，这个 GitHub 整理了几百本常用技术PDF，绝大部分核心的技术书籍都可以在这里找到，GitHub地址：https://github.com/iamshuaidi/CS-Book（电脑打开体验更好），地址阅读原文直达