本文主要是介绍Leetcode的中等算法题：198. 打家劫舍，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接：https://leetcode.cn/problems/house-robber/

方法1

学会了动态规划思路后，我独立想出来的一个方法，缺点是代码不够优雅（dp和nums的序号有错位）。

我的代码

int max(int a,int b){
    return a>b?a:b;
}
int rob(int* nums, int numsSize){
    // dp预留出来2个位置.dp[i+2]表示num[]偷到第i个（下标计数）房屋时的最高金额
    int dp[103],res=nums[0];
    int j=2;//用j表示dp的下标
    dp[0] = dp[1] = 0;
    dp[j] = nums[0];
    for(int i=1;i<numsSize;i++){
        j = i+2;
        dp[j] = max(dp[j-3]+nums[i],dp[j-2]+nums[i]);
        res = max(dp[j],dp[j-1]);
    }
    return res;
}

提交结果

执行结果：
通过
显示详情
添加备注

执行用时：
0 ms
, 在所有 C 提交中击败了
100.00%
的用户
内存消耗：
5.7 MB
, 在所有 C 提交中击败了
63.14%
的用户
通过测试用例：
68 / 68

思路

状态数组dp[]存放抢了第i个（下标计）房屋抢劫时，所抢到的最大金额。注意，并不一定抢到前i个房屋时的最大金额，因为抢到第i-1时更大呢。

抢到第i个时，上一个抢的应该是第i-2或第i-3个房屋。因为不能连续，所以不能是i-1，但也不一定就是i-2，也可以是i-3啊。i-4就没必要了，如果算i-4就肯定少算了与之间隔的i-2。

代码的dp[]下标用j表示，并不与nums的i相同，采取了错位的方法。没那么优雅了。

方法2

也是动态规划的方法，与我独立想出来的不同点有二，一是在for循环中使用了临界判断，虽然加大了运算消耗，但是避免了dp[]与nums[]的错位；二是dp[]直接以结果为导向，dp[i]直接记录抢到前i个房屋时的最大金额。我一拍脑门，优化了一的缺点。可以看一看我和up主代码的不同点。
参考：https://www.bilibili.com/video/BV14b4y177DM?p=1&t=122.2

我优化后的代码

int max(int a,int b){
    return a>b?a:b;
}
int rob(int* nums, int numsSize){
    int dp[110];
    dp[0] = nums[0];
    if(numsSize>1){
        dp[1] = max(nums[0],nums[1]);
    }
    for(int i=2;i<numsSize;i++){
        dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
    }
    return dp[numsSize-1];
}

提交结果

执行结果：
通过
显示详情
添加备注

执行用时：
0 ms
, 在所有 C 提交中击败了
100.00%
的用户
内存消耗：
5.6 MB
, 在所有 C 提交中击败了
84.31%
的用户
通过测试用例：
68 / 68

思路

初始状态：

dp[0] = nums[0];
dp[1] = max(nums[0],nums[1]);

状态方程：

dp[i] = max(dp[i-1],dp[i-2]+nums[i]);

抢到第i个时，看一看dp[i-1]与dp[i-2]+nums[i]谁大，dp[i-1]表示抢到第i-1个时最大金额，dp[i-2]表示抢到第i-2个时最大金额，nums[i]表示第i个房屋的金额。dp[i-2]+nums[i]表示抢第i个房屋时的金额，但不一定是最大金额，所以与dp[i-1]做比较。

这篇关于Leetcode的中等算法题：198. 打家劫舍的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！