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屋！