打家劫舍 中等🌟🌟🌟🌟🌟
问题描述
原文链接：198.打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
示例 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 <= 1000 <= nums[i] <= 400
代码实现
Java
class Solution {
public int rob(int[] nums) {
if(nums.length <= 1){
return nums[0];
}
if(nums.length <= 2){
return Math.max(nums[0], nums[1]);
}
int[] dp = new int[nums.length];
// 初始值
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
// dp[i] = max(nums[i] + dp[i-2], dp[i-1]);
for(int i = 2; i < nums.length; i++){
dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
}
return dp[nums.length-1];
}
}
Python
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 1:
return nums[0]
if len(nums) <= 2:
return max(nums[0], nums[1])
dp = [0] * len(nums)
# 初始值
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
# dp[i] = max(nums[i] + dp[i-2], dp[i-1])
for i in range(2, len(nums)):
dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])
return dp[-1]
C++
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() <= 1) {
return nums[0];
}
if (nums.size() <= 2) {
return max(nums[0], nums[1]);
}
vector<int> dp(nums.size(), 0);
// 初始值
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
// dp[i] = max(nums[i] + dp[i-2], dp[i-1])
for (int i = 2; i < nums.size(); i++) {
dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]);
}
return dp[nums.size() - 1];
}
};
Go
func rob(nums []int) int {
if len(nums) <= 1 {
return nums[0]
}
if len(nums) <= 2 {
return max(nums[0], nums[1])
}
dp := make([]int, len(nums))
// 初始值
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
// dp[i] = max(nums[i] + dp[i-2], dp[i-1])
for i := 2; i < len(nums); i++ {
dp[i] = max(nums[i] + dp[i-2], dp[i-1])
}
return dp[len(nums)-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}