#P4090. 打家劫舍
-
ID: 2327
Tried: 99
Accepted: 42
Difficulty: 5
-
算法标签>动态规划
打家劫舍
题目内容
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
输入描述
一个代表每个房屋存放金额的非负整数数组
输出描述
一个整数表示一夜之内能够偷窃到的最高金额。
样例1
输入
1 2 3 1
输出
4
说明
偷窃 1 号房屋 (金额 =1) ，然后偷窃 3号房屋 (金额=3)。
偷窃到的最高金额 =1+3=4 。
样例2
输入
2 7 9 3 1
输出
12
说明
偷窃 1 号房屋 (金额=2), 偷窃3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 =1)。
偷窃到的最高金额 =2+9+1=12。
提示：
- 1<=nums.length<=100
- 0<=nums[i]<=400
题解
题面描述
给定一个数组 nums，其中 nums[i] 表示第 i 个房屋中的现金。你是一个专业的小偷，在一夜之间计划偷窃这些房屋，但如果偷窃相邻的两个房屋就会触发报警系统。要求在不触动报警装置的前提下，求出一夜之内能够偷窃到的最高金额。
思路
本题可以使用动态规划解决。我们定义数组 dp，其中 dp[i] 表示偷到第 i 个房屋时所能获得的最高金额。状态转移方程为
dp[i]=max(dp[i−1], dp[i−2]+nums[i])其中，dp[i−1] 表示不偷第 i 个房屋时的最大金额，而 dp[i−2]+nums[i] 表示偷第 i 个房屋时的金额。初始条件为
dp[0]=nums[0]和
dp[1]=max(nums[0], nums[1])最终答案即为 dp[n−1]，其中 n 为数组长度。
代码分析
- 时间复杂度：O(n)，其中 n 为房屋数量，只需遍历一次数组。
- 空间复杂度：O(n)，我们使用一个数组 dp 保存中间状态。如果对空间有要求，也可以将空间优化到常数级。
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 使用 Solution 类封装功能函数
class Solution {
public:
// 函数 rob 实现偷窃功能，返回最高可偷金额
int rob(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0; // 没有房屋时返回 0
if(n == 1) return nums[0]; // 只有一个房屋时直接返回其金额
// 动态规划数组 dp，dp[i] 表示偷到第 i 个房屋时的最高金额
vector<int> dp(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
// 状态转移：对于每个房屋，选择偷或者不偷
for (int i = 2; i < n; i++){
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[n-1];
}
};
int main(){
vector<int> nums;
int x;
// 读入一行输入的房屋金额
while(cin >> x) {
nums.push_back(x);
}
Solution solution;
cout << solution.rob(nums);
return 0;
}
Python
# 定义 Solution 类封装功能函数
class Solution:
def rob(self, nums):
n = len(nums)
if n == 0:
return 0 # 无房屋返回 0
if n == 1:
return nums[0] # 只有一个房屋时直接返回金额
# 初始化动态规划数组 dp，dp[i] 表示偷到第 i 个房屋时的最高金额
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
# 状态转移，选择偷或者不偷当前房屋
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
if __name__ == "__main__":
import sys
# 从标准输入中读入数据，输入为一行整数
nums = list(map(int, sys.stdin.read().split()))
solution = Solution()
print(solution.rob(nums))
Java
import java.util.*;
// 主类 Main
public class Main {
// 定义内部静态类 Solution 封装功能函数
static class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n == 0) return 0; // 无房屋时返回 0
if(n == 1) return nums[0]; // 只有一个房屋时直接返回金额
// 动态规划数组 dp，dp[i] 表示偷到第 i 个房屋时的最高金额
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
// 状态转移
for (int i = 2; i < n; i++){
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[n-1];
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
// 读入输入的所有整数
while(sc.hasNextInt()){
list.add(sc.nextInt());
}
int[] nums = new int[list.size()];
for (int i = 0; i < list.size(); i++){
nums[i] = list.get(i);
}
Solution sol = new Solution();
System.out.println(sol.rob(nums));
}
}