Leetcode 盗贼 [英] Leetcode House robber
问题描述
我正在尝试关于 leet 代码的 House Robber 问题(dp 问题).来自 GYX 用户之一的这个解决方案看起来简单而优雅.
I was trying House Robber problem(dp problem) on leet code. This solution from one of the user GYX looks simple and elegant.
int rob(vector<int>& num) {
int n = num.size();
if (n==0) return 0;
vector<int> result(n+1,0);
result[1] = num[0];
for (int i=2;i<=n;i++){
result[i] = max(result[i-1],result[i-2]+num[i-1]);
}
return result[n];
}
但我就是无法理解这个逻辑.请帮助我了解逻辑以及如何解决此类问题?
But I just could not get my head around the logic. Please help me with the logic and also how to approach problems like this?
推荐答案
假设我将金额存储在 house[k]
中的第 k 个房子.
Suppose I store the amount in kth house in house[k]
.
假设现在我在 max[k]
中存储了从前 k 个房屋(并且仅前 k 个)中可以掠夺的最大金额.
Suppose now I store the maximum amount of money possible to loot from the first k houses(and first k only) in max[k]
.
现在考虑没有房子,所以max[0]=0
Now consider no houses, so max[0]=0
现在只考虑第一个房子,max[1]
=房子 1 的数量
Now considering only first house, max[1]
=amount in house 1
现在考虑前两套房子,
max[2]
={either max[1]
(暗示我们选择掠夺房屋 1)或(房屋 2 的数量 + 我掠夺的最大数量直到房子位于我现在的房子之前 2 个地方)}={max(max[1],house[2]+max[0])}
max[2]
={either max[1]
(implies we chose to loot house 1) or (amount in house 2 + maximum amount that I had looted until the house located 2 places before my current house)}={max(max[1],house[2]+max[0])}
前3个房子类似,max[3]=max(max[2],house[3]+max[1])
观察这个趋势,可以表述为max[k]=max(max[k-1],house[k]+max[k-2])
.这个值一直计算到最后当没有更多房子的时候,我们得到前n个房子可以掠夺的最大数量.
Observing this trend, it can be formulated that max[k]=max(max[k-1],house[k]+max[k-2])
. This value is calculated till in the end when there are no more houses, we get the maximum amount that can be looted from these first n houses.
DP 问题只有在您之前有过一些练习和熟悉的情况下才会出现,这总是有帮助的.
DP problems strike the head only when you have had some practice and familiarity before, and this always helps.
这篇关于Leetcode 盗贼的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!