LeetCode 198—— 打家劫舍

本文主要是介绍LeetCode 198—— 打家劫舍，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目

2. 解题思路

此题使用动态规划求解，假设 $dp[i][0]$ 代表不偷窃第 $i$ 个房屋可以获得的最高金额，而 $dp[i][1]$ 代表偷窃第 $i$ 个房屋可以获得的最高金额。那么转移方程为：

$$dp[i+1][0]=max(dp[i][0],dp[i][1])$$

不偷窃第 $i+1$ 个房屋时，第 $i$ 个房屋可以偷也可以不偷，所以取二者的最大值。

$$dp[i+1][1]=dp[i][0]+nums[i+1]$$

要偷窃第 $i+1$ 个房屋的话，第 $i$ 个房屋一定不可以偷，所以取前一个房间不偷窃可以获得的最大金额再加上当前房屋的价值。

由于 $dp[i+1]$ 只和 $dp[i]$ 有关系，所以，我们只需要两个状态值即可。

时间复杂度为 $O(n)$，空间复杂度为 $O(1)$.

3. 代码实现

class Solution {
public:int rob(vector<int>& nums) {int stole_value = 0;int not_stole_value = 0;int max_value = 0;for (int i = 0; i < nums.size(); ++i) {int temp = not_stole_value;not_stole_value = max(stole_value, not_stole_value);stole_value = temp + nums[i];max_value = max(max_value, stole_value);}return max_value;}
};

这篇关于LeetCode 198—— 打家劫舍的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---