Open azl397985856 opened 2 years ago
动态规划经典问题。
背包类
问题, 考虑“选或不选” 。
根据题意, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警, 故不能同时抢两个相邻的房间。
dp[i]: 从第 i 间房子开始抢劫, 最多能抢到的钱。
从房间i开始抢, 如果选nums[i], 另外由于不能同时抢两个相邻的房间, 故最近的可抢的房间是房间i+2, 于是最多能抢到的钱为 dp[i + 2] + nums[i];
从房间i开始抢, 如果不选nums[i], 最近的可抢的房间是房间i+1, 从房间i开始抢最多能抢到的钱为dp[i + 1]。
实现语言: C++
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
// dp[i]: 从第 i 间房子开始抢劫, 最多能抢到的钱
vector<int> dp(n + 2, 0); /* base case: dp[n] = 0; 于是dp[n]和dp[n+1] 都应该初始化为0 */
for (int i = n - 1; i >= 0; i--)
{
dp[i] = max(dp[i + 1], dp[i + 2] + nums[i]); /* 从房间i开始抢, 如果选nums[i]最多能抢到的钱为 dp[i + 2] + nums[i]; 从房间i开始抢, 如果不选nums[i], 从房间i开始抢最多能抢到的钱为dp[i + 1] */
}
return dp[0];
}
};
class Solution:
def rob(self, nums: List[int]) -> int:
'''
对于 第 [i] 个房子,抢还是不抢(判断总价值哪个更大)
i - 1 不能抢,否则会触发警铃
抢: 当前房子的价值 + dp[i-2]
不抢: dp[i-1]
当前房子的价值就是上面对应的抢或者不抢中间的那个较大的值
dp[i] = max(dp[i-1], dp[i-2] + nums[i-2)
由于 dp[0] 和 dp[1] 会初始化为 0,所以 dp[i] 对应的是 nums[i-2]
complexity
Time O(n)
Space O(n)
系列题: House Robber 198/213/337
'''
n = len(nums)
if n < 3:
return max(nums)
dp = [0] * (n+2)
for i in range(2, n+2):
dp[i] = max(dp[i-1], dp[i-2]+nums[i-2])
return dp[-1]
'''
method 2 memoize
状态分解:
抢当前房子; func(i+2) + nums[i]
抢下一个房子; func(i+1)
time: O(n)
space: O(n)
'''
memo = {}
def memoize(i):
if i >= len(nums):
return 0
if i in memo:
return memo[i]
res = max(memoize(i+1), memoize(i+2) + nums[i])
memo[i] = res
return res
return memoize(0)
class Solution {
public int rob(int[] nums) {
int count = 0;
if(nums.length == 0){
return 0;
}
if(nums.length == 1){
return nums[0];
}
int[] s = new int[nums.length];
s[0] = nums[0];
s[1] = Math.max(nums[0],nums[1]);
for(int i=2; i< nums.length; i++){
s[i] = Math.max(s[i-1], s[i-2]+nums[i]);
}
return s[nums.length-1];
}
}
temp = prev1;
prev1 = max(prev2 + nums[i], prev1);
prev2 = temp;
Language: Java
public int rob(int[] nums) {
// Let prev1 and prev2 be the total money at i-1
// and i-2 house when current house is i
int prev1 = 0;
int prev2 = 0;
for (int num : nums) {
int temp = prev1;
prev1 = Math.max(prev2 + num, prev1);
prev2 = temp;
}
return prev1;
}
dfs + memo O(n), O(n)
class Solution:
def rob(self, nums: List[int]) -> int:
@cache
def dfs(idx):
if idx >= len(nums): return 0
return max(nums[idx] + dfs(idx+2), dfs(idx+1))
return dfs(0)
dp[i] means maximum money I can get at pos i, for the pos i, I can rob or not rob. dp[i] = Math.max(dp[i - 1], dp[i] + dp[i - 2]), corner case is i == 1
class Solution {
public int rob(int[] nums) {
int len = nums.length;
for (int i = 1; i < len; i++) {
if (i == 1) nums[i] = Math.max(nums[i], nums[i - 1]);
else nums[i] = Math.max(nums[i - 1], nums[i - 2] + nums[i]);
}
return nums[len - 1];
}
}
class Solution(object):
def rob(self, nums):
if len(nums)==0:
return 0
elif len(nums) == 1:
return nums[0]
elif len(nums) == 2:
return max(nums)
else:
rob1 = nums[0]
rob2 = nums[1]
for i in range(2,len(nums)):
temp = rob1
rob1 = max(rob1, rob2)
rob2 = max(nums[i]+temp, rob2)
return max(rob1, rob2)
var rob = function(nums) {
const length = nums.length;
if (length == 0){
return 0;
}else if (length == 1){
return nums[0];
}else if (length == 2){
return Math.max(nums[0],nums[1]);
}else{
let rob1 = nums[0];
let rob2 = nums[1];
let temp = 0;
for (let i=2; i<length; i++){
temp = rob1;
rob1 = Math.max(rob1, rob2);
rob2 = Math.max(nums[i]+temp, rob2);
};
return Math.max(rob1, rob2);
};
};
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums: return 0
if len(nums) < 3: return max(nums)
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
return dp[-1]
time complexity: O(n) space complexity: O(n)
Java Code:
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n == 1)return nums[0];
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 - 2] + nums[i],dp[i - 1]);
}
return dp[n-1];
}
}
复杂度分析
令 n 为数组长度。
Problem Link
Ideas
Complexity: hash table and bucket
Code
#dp, dp[n - 2] + nums[n], dp[n - 1]
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1: return nums[0]
elif len(nums) == 2: return max(nums[0], nums[1])
else:
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
class Solution:
def rob(self, nums: List[int]) -> int:
length = len(nums)
if length == 1:
return nums[0]
else:
prev = nums[0]
cur = max(prev, nums[1])
for i in range(2, length):
cur, prev = max(prev + nums[i], cur), cur
return cur
public int rob(int[] nums) {
int n = nums.length;
int[] rob = new int[n];
int[] no_rob = new int[n];
rob[0] = nums[0];
for (int i = 1; i < n; i++) {
rob[i] = no_rob[i-1] + nums[i];
no_rob[i] = Math.max(rob[i-1], no_rob[i-1]);
}
return Math.max(rob[n-1], no_rob[n-1]);
}
dp(i)
偷第i
个房子的最大收益dp(0) = 0; dp(1) = house[0]
转移方程:对于第i
个房子,
dp(i) = dp(i-2) + house[i-1]
dp(i) = dp(i-1)
综上,dp(i) = max(dp(i-1), dp(i-2) + house[i-1])
class Solution {
public int rob(int[] nums) {
int n = nums.length;
// int[] dp = new int[n + 1];
int[] dp = new int[3]; // 滚动数组降低空间复杂度
dp[1] = nums[0];
for (int i=2; i<=n; i++) {
//dp[i] = Math.max(dp[i-2] + nums[i-1], dp[i-1]);
dp[i % 3] = Math.max(dp[(i-2) % 3] + nums[i-1], dp[(i-1) % 3]); // 滚动数组
}
// return dp[n];
return dp[n % 3];
}
}
动态规划
class Solution {
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < dp.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[dp.length - 1];
}
}
class Solution {
public int rob(int[] nums) {
int[] dp = new int[nums.length + 1];
dp[1] = nums[0];
for (int i = 2; i < dp.length; i++){
dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
}
return dp[dp.length - 1];
}
}
Time Complexity: O(n), Space Complexity: O(n)
dp[i] 代表在前 i 间屋子偷能偷到的最大值
base case: dp[0] = nums[0] 因为只有屋子0, dp[1] = max(nums[0], nums[1]) 因为只有屋子1和2
状态转移: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 分别代表不抢house i和抢house i
return: 返回 dp[-1]
class Solution:
def rob(self, nums: List[int]) -> int:
dp = [0] * len(nums)
dp[0] = nums[0]
if len(nums) >= 2:
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
时间复杂度: O(n) 遍历数组的复杂度
空间复杂度: O(n) dp 数组的复杂度
如果使用i-2以及i,比较只使用i-1,取大的
class Solution:
def rob(self, nums: List[int]) -> int:
dp = [0] * (len(nums) + 2)
dp[0] = 0
dp[1] = 0
for i in range(2, len(nums) + 2):
dp[i] = max(dp[i - 2] + nums[i - 2], dp[i-1])
return dp[-1]
时间复杂度 :O(N)
空间复杂度:O(N)
Java Code:
class Solution {
public int rob(int[] nums) {
// dp[i]: the maximum amount to rob i houses
// i grow length
int n = nums.length;
if (n == 1) {
return nums[0];
}
int prev1 = 0;
int prev2 = nums[0];
for (int i = 2; i <= n; i++) {
int temp = prev2;
prev2 = Math.max(prev1 + nums[i - 1], prev2);
prev1 = temp;
}
return prev2;
}
}
// time: O(n) space: O(1)
class Solution {
public int rob(int[] nums) {
// dp[i]: the maximum amount to rob i houses
// i grow length
int n = nums.length;
if (n == 1) {
return nums[0];
}
int[] dp = new int[n + 1];
dp[0] = 0; dp[1] = nums[0];
for (int i = 2; i <= n; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
}
return dp[n];
}
}
// O(n) O(n)
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
// dp[i]: 从第 i 间房子开始抢劫, 最多能抢到的钱
vector<int> dp(n + 2, 0); /* base case: dp[n] = 0; 于是dp[n]和dp[n+1] 都应该初始化为0 */
for (int i = n - 1; i >= 0; i--)
{
dp[i] = max(dp[i + 1], dp[i + 2] + nums[i]); /* 从房间i开始抢, 如果选nums[i]最多能抢到的钱为 dp[i + 2] + nums[i]; 从房间i开始抢, 如果不选nums[i], 从房间i开始抢最多能抢到的钱为dp[i + 1] */
}
return dp[0];
}
};
Explanation
Python
class Solution:
# Approach 1 (space O(n))
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
elif len(nums) == 2:
return max(nums)
else:
dp = [0 for _ in range(len(nums))]
dp[0], dp[1] = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
return max(dp[-1], dp[-2])
# Approach 2 (space O(1))
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
elif len(nums) == 2:
return max(nums)
else:
prevprev, prev = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
temp = max(prev, prevprev+nums[i])
prevprev = prev
prev = temp
return max(prev, prevprev)
Complexity:
O(n)
O(n) / O(1)
动态规划 dp[i] 表示到第i个家庭的时候,所能抢劫的最大值 dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]) 因为不能抢劫相邻的房子 到达当前房子的时候抢的钱有两种情况,一种是当前房子要抢,那么与他相邻的i - 1 房子就不能抢,另一种是当前房子不抢,那 i-1就可以抢
class Solution:
def rob(self, nums: List[int]) -> int:
# state
# dp[i] 表示到第i个家庭的时候,所能抢劫的最大值
# dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]) 因为不能抢劫相邻的房子
# 到达当前房子的时候抢的钱有两种情况,一种是当前房子要抢,那么与他相邻的i - 1 房子就不能抢,另一种是当前房子不抢,那 i-1就可以抢
if len(nums) <= 1:
return nums[0]
dp = [0] * len(nums)
# initialize
dp[0] = nums[0]
dp[1] = max(nums[1], nums[0])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
return dp[len(nums) - 1]
时间复杂度:O(n) 空间复杂度:O(n)
time(N)
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums) + 2
dp = [0] * n
maxi = -float('inf') # store MAX on the go
for i in range(2, n):
"""
2 options:
1. take nothing, carry over money from last house
2. rob 'em! carry over money from 2 houses ago + this house's money
"""
dp[i] = max(dp[i-1], dp[i-2] + nums[i-2])
maxi = max(maxi, dp[i])
return maxi
class Solution {
public int rob(int[] nums) {
if(nums.length ==1){
return nums[0];
}
if (nums.length==2){
return Math.max(nums[1],nums[0]);
}
int [] dp = new int[nums.length];
Arrays.fill(dp,0);
dp[0] = nums[0];
dp[1] = Math.max(nums[1],nums[0]);
int res=0;
for(int i=2; i<nums.length; i++){
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
res = Math.max(dp[i], res);
}
return res;
}
}
经典动规题
把dp[i]当成是从0到i的最优结果,动规关系则有:dp[i]=max(dp[i-3],dp[i-2])+nums[i],把dp[0],dp[1],dp[2]初始化为nums[0],nums[1],nums[0] + nums[2],遍历dp,返回dp最后两个元素中的最大值即可(因为元素都为正整数,所以最后两个一定有最大值)
刚刚和同学讨论了题解的动规方程dp[i]=max(dp[i-1],dp[i-2]+nums[i])
,虽然在这个题目中是等价的,但果然还是这个更加合理一点。因为题目给出了一定是整数的情况,所以我的假设是:"nums[i]一定是有i-2
或者i-3
跳过来的",实际情况是,如果存在负数的话(小偷进房间捐钱),那为了避免丢钱就不一定是从i-2
或i-3
跳过来的了。题解的就可以避免这个尴尬,因为它一定要么就是dp[i-1],要么就是从上一格跳过来的。
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
elif len(nums) == 2:
return max(nums[0], nums[1])
else:
dp = [0] * len(nums)
dp[0], dp[1], dp[2] = nums[0], nums[1], nums[0] + nums[2]
for i in range(3, len(dp)):
dp[i] = max(dp[i - 3], dp[i - 2]) + nums[i]
return max(dp[-1], dp[-2])
负数case也能解的代码
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
elif len(nums) == 2:
return max(nums[0], nums[1])
else:
dp = [0] * len(nums)
dp[0], dp[1] = max(dp[0], nums[0]), max(dp[0], nums[0], nums[1])
for i in range(2, len(dp)):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return max(dp[-1], dp[-2])
时间复杂度O(N)
空间复杂度O(N)
其实空间复杂度可以优化为O(1),即不另使用dp,而是直接在nums上操作
https://leetcode.com/problems/house-robber/
const rob = function(nums) {
if (!nums.length) return 0;
if (nums.length === 1) return nums[0];
if (nums.length === 2) return Math.max(nums[0], nums[1]);
let maxAtTwoBefore = nums[0];
let maxAtOneBefore = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
const maxAtCurrent = Math.max(nums[i] + maxAtTwoBefore, maxAtOneBefore);
maxAtTwoBefore = maxAtOneBefore;
maxAtOneBefore = maxAtCurrent;
}
return maxAtOneBefore;
};
class Solution:
def rob(self, nums: List[int]) -> int:
dp = [0] * len(nums)
if len(nums) < 3: return max(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(nums[i] + dp[i-2], max(dp[i-1], dp[i-2]))
return dp[-1]
class Solution {
// dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
int a = nums[0];
int b = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
int temp = b;
b = Math.max(b, a + nums[i]);
a = temp;
}
return b;
}
}
dp
使用语言:Python3
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
length = len(nums)
max_r = [0] * (length + 1)
max_r[length - 1] = nums[length - 1]
for i in range(length - 2, -1, -1):
max_r[i] = max(max_r[i + 1], max_r[i + 2] + nums[i])
return max_r[0]
复杂度分析 时间复杂度:O(n) 空间复杂度:O(n)
C++ Code:
class Solution {
public:
int rob(vector<int>& nums) {
// define robe x to obtain max value as dp function.
// dp(x) = max(num[x] + dp(x-2), dp(x-1))
vector<int> dp(nums.size()+2, 0);
for(int i=0; i< nums.size(); i++)
{
dp[i+2] = max(nums[i] + dp[i], dp[i+1]);
}
return dp[nums.size()+1];
}
};
class Solution {
public:
int rob(vector<int>& nums) {
// define robe x to obtain max value as dp function.
// dp(x) = max(num[x] + dp(x-2), dp(x-1))
vector<int> dp(2, 0);
for(int i=0; i< nums.size(); i++)
{
int current = max(nums[i] + dp[0], dp[1]);
dp[0] = dp[1];
dp[1] = current;
}
return dp[1];
}
};
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
dp = [0 for i in range(n + 1)]
dp[0] = 0
dp[1] = nums[0]
for i in range(2, n + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
return dp[n]
# dp[i] = max(dp[i - i], dp[i - 2] + values[i])
C++ Code:
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() <= 0) {
return 0;
}
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]);
for (int i = 2; i < nums.size(); ++i) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.size() - 1];
}
};
复杂度分析
令 n 为数组长度。
dp[i][1] 表示前i个房子偷第i个房子的最大收益
dp[i][0] 表示前i个房子不偷第i个房子的最大收益
dp[i]0] = max(dp[i-1][0],dp[i-1][1])
dp[i][1] = dp[i-1][0] + nums[i]
可以用滚动数组优化
class Solution:
def rob(self, nums: List[int]) -> int:
dp = [[0, nums[0]]]
for i in range(1, len(nums)):
dp.append([0, 0])
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
dp[i][1] = dp[i - 1][0] + nums[i]
return max(dp[-1])
Time O(n)
Space O(n)
答应我,不偷也不抢,好吗!
var rob = function(nums) {
return 0;
}
动态规划
状态方程如下:
f[n] = max(f[n - 1], f[n - 2] + nums[n - 1])
上一次抢了,那这一次就不抢
上一次没抢,那就是上上次和这一次抢
取这两个中的最大值为结果
var rob = function(nums) {
let n = nums.length;
let f = [0, nums[0]];
for (let i = 2; i <= n; i++) {
f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]);
}
return f[n];
};
动态规划。每个房子两个选择,选这一家,结合前前家的结果,或者不选,直接选择前一家的结果。
class Solution:
def rob(self, nums: List[int]) -> int:
n=len(nums)
if n==0:
return 0
if n==1:
return nums[0]
a,b=nums[0],max(nums[0],max(nums[0],nums[1]))
for i in range(2,n):
c=max(b,a+nums[i])
a,b=b,c
return b
时间复杂度:O(n)
空间复杂度:O(1)
动态规划
JavaScript Code
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function (nums) {
// Tag: DP
const dp = [];
dp[0] = 0;
dp[1] = 0;
for (let i = 2; i < nums.length + 2; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i - 2], dp[i - 1]);
}
return dp[nums.length + 1];
};
复杂度
动态规划 dp[i]=max(dp[i-1],dp[i-2]+nums[i])
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.empty())
return 0;
int len=nums.size();
if(len==1)
return nums[0];
vector<int>dp(len,0);
dp[0]=nums[0];
dp[1]=max(nums[0],nums[1]);
for(int i=2;i<len;i++){
dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[len-1];
}
};
复杂度分析
思路: 失败,没能从昨天的题目联想。本质还是一个爬楼梯的动态规划。 不同的是昨天是在前两个位置上取个最小值加上自己本身,即dp[i] = min(dp[i-2],dp[i-1])+nums[i] 。且需要多给dp数组留一个空间。 而今天的关键是不能相邻,且是最大值,所以dp[i] = min(dp[i-2]+nums[i]+dp[i-1]),且需要dp数组留出两个空间,保证倒数第一位和倒数第二位都有可能成为答案。 最后,空间复杂度1的解法中有一个有意思的地方:可以直接从0~n-1进行遍历,用一个临时值temp存储b的值,b获取最大值后,把temp的值给a。实现旋转赋值
func rob(nums []int) int {
n := len(nums)
dp := make([]int,n+2)
if len(nums) == 1{
return nums[0]
}
dp[0] = 0
dp[1] = 0
for i:=2;i<n+2;i++{
dp[i] = max(dp[i-2]+nums[i-2],dp[i-1])
}
return dp[n+1]
}
func max(a, b int) int{
if a > b{
return a
}else{
return b
}
}
/***********/
func rob(nums []int) int {
a,b:=0,0
for i:=0;i<len(nums);i++{
temp := b
b = max(a+nums[i],b)
a = temp
}
return b
}
func max(a, b int) int{
if a > b{
return a
}else{
return b
}
}
时间复杂度O(n) 空间复杂度O(n)和O(1)
Algo
- Backward
class Solution:
def rob(self, nums: List[int]) -> int:
# recur equaltion: income(i) = max(income(i+1), income(i+2)+nums(i))
# boundary: income[-1] = nums[-1], income[-2] = max(nums[-2], nums[-1])
if len(nums) == 1: return nums[0]
if len(nums) == 2: return max(nums)
income = [0 for _ in range(len(nums))]
income[-1], income[-2] = nums[-1], max(nums[-1], nums[-2])
for i in range(len(nums)-3, -1, -1): income[i] = max(income[i+1], income[i+2] + nums[i])
return max(income)
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp_res = [0]*(n+1)
dp_res[n-1] = nums[n-1]
for i in range(n-2,-1,-1):
t1 = dp_res[i+1]
t2 = dp_res[i+2] + nums[i]
dp_res[i] = max(t1, t2)
return dp_res[0]
Similar to yesterday, but in reverse order
Time: O(N)
Space: O(N)
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int first = nums[0], second = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}
}
时间复杂度:O(N) 空间复杂度:O(1)
Dynamic Programming. Transit function: dp[i] = max(dp[0:i-1]) + nums[i]. The complexity of max(dp[0:i-1]) will be O(N), so we need to think whether we can record the max value we've seen before i-1 th element. The answer is yes. Becasue we scan the array from left to right, every time for i-th element, after we update its value, if it's larger than current max value, then for i+2-th element we will use updated max value. When we update i-th element, we will use the max(max value, i-2 th element) to see update it.
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
if n <= 2:
return max(nums)
cur_max = nums[0]
dp0, dp1 = nums[0], nums[1]
for i in range(2, n):
tmp = 0
if i% 2 == 0:
tmp = dp0
dp0 = max(dp0, cur_max) + nums[i]
else:
tmp = dp1
dp1 = max(dp1, cur_max) + nums[i]
cur_max = max(cur_max, tmp)
return max(dp0, dp1)
Time: O(N) Space: O(1)
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
示例 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 。
动态规划
状态转移方程:maxTotalAmount[i] = max{nums[i] + maxTotal[i-2], maxTotal[i-1]}
我的房屋是看下标,就是1号房屋下标是0,maxTotalAmount[i]是偷到下标为i的房屋所拿到的最大金额,注意这里可以偷i下标房屋,也允许不偷它
class Solution {
public int rob(int[] nums) {
//动态规划
int size = nums.length;
//特殊处理
if(size == 1){
return nums[0];
}
int[] maxTotalAmount = new int[size];
maxTotalAmount[0] = nums[0];
maxTotalAmount[1] = Math.max(nums[0],nums[1]);
//状态转移方程
//maxTotalAmount[i] = max{nums[i] + maxTotal[i-2], maxTotal[i-1]}
for(int i = 2; i < size; i++){
maxTotalAmount[i] = Math.max(maxTotalAmount[i-2] + nums[i],maxTotalAmount[i-1]);
}
return maxTotalAmount[size-1];
}
}
时间复杂度:$O(n)$
空间复杂度:$O(n)$
# time: O(N)
# space: O(1)
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums[0], nums[1])
prev1 = nums[0]
prev2 = max(nums[0], nums[1])
curr = prev2
for i in range(2, len(nums)):
curr = max(prev2, prev1 + nums[i])
prev1 = prev2
prev2 = curr
return curr
// 到第k个房间的最高金额
// dp[k] = Math.max(dp[k-2] + nums[k], dp[k-1])
var rob = function (nums) {
let len = nums.length;
if (len === 0) return 0;
if (len === 1) return nums[0];
let first = nums[0];
let second = Math.max(nums[1], nums[0]);
for (let i = 2; i < len; i++) {
let temp = second;
second = Math.max(second, first + nums[i]);
first = temp;
}
return second;
};
定义dp[i]是在i位置最多能够抢到的钱,只和i-1,i-2相关,偷了i-1就不能偷i,偷了i-2可以偷i。所以dp[i] = max(dp[i-1], dp[i-2]+nums[i])
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0], dp[1] = nums[0], max(nums[0], nums[1]) # 这里dp[1]不是nums[1]一开始写错了
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
return dp[-1] # 这里不用max(dp[-1],dp[-2]) 因为停在-2的话也会被-1位置记录的
var rob = function(nums) {
let dp=[];
if(nums.length===1)return nums[0]
if(nums.length===2)return Math.max(nums[0],nums[1])
dp[0]=nums[0];
dp[1]=Math.max(nums[0],nums[1]);
for(let i=2;i<nums.length;i++){
dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i])
}
return dp[nums.length-1]
};
198. 打家劫舍
https://leetcode-cn.com/problems/min-cost-climbing-stairs/
def rob(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
# 子问题:
# f(k) = 偷 [0..k) 房间中的最大金额
# f(0) = 0
# f(1) = nums[0]
# f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }
N = len(nums)
dp = [0] * (N+1)
dp[0] = 0
dp[1] = nums[0]
for k in range(2, N+1):
dp[k] = max(dp[k-1], nums[k-1] + dp[k-2])
return dp[N]
动态规划,小偷当前i可以偷,i-1不能偷,i-2可以偷,因此可以算出dp[i] = Math.max(dp[i-2]+nums[i-1],dp[i-1]);
var rob = function(nums) {
if(!nums.length) return 0;
const len = nums.length;
let dp = new Array(len+1);
dp[0] = 0;
dp[1] = nums[0];
for(let i = 2; i <= len;i++){
dp[i] = Math.max(dp[i-2]+nums[i-1],dp[i-1]);
}
return dp[len];
};
动态规划,第 i 天有两种状态, 并且由 i - 1 天转移来
class Solution {
public int rob(int[] nums) {
int[][] dp = new int[nums.length][2];
// 初始化basecase
dp[0][0] = 0;
dp[0][1] = nums[0];
for (int i = 1; i < nums.length; ++i) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + nums[i];
}
return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
}
}
C++ Code:
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==1)
return nums[0];
int dp1 = nums[0], dp2 = nums[1];
for(int i=2;i<nums.size();i++)
{
int temp = max(dp2,dp1+nums[i]);
dp1 = max(dp1,dp2);
dp2 = temp;
}
return max(dp1,dp2);
}
};
复杂度分析
令 n 为数组长度。
【思路】 动态规划,有两种状态。 参考评论区大佬
class Solution {
public int rob(int[] nums) {
int count = 0;
if(nums.length == 0){
return 0;
}
if(nums.length == 1){
return nums[0];
}
int[] s = new int[nums.length];
s[0] = nums[0];
s[1] = Math.max(nums[0],nums[1]);
for(int i=2; i< nums.length; i++){
s[i] = Math.max(s[i-1], s[i-2]+nums[i]);
}
return s[nums.length-1];
198. 打家劫舍
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/house-robber/
前置知识
暂无
题目描述