Leetcode房子劫匪

我试图House Robber问题（dp问题）上的代码。来自用户GYX的解决方案看起来简单而优雅。Leetcode房子劫匪

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]; 
    }

但我只是无法让我的头在逻辑。请帮助我理解逻辑，以及如何解决这样的问题？

来源

2016-09-17 roang

假设我在house[k]中存储第k个房屋的金额。

现在假设我在max[k]中储存了可能从最初的k个房屋（和仅前k个）中掠夺的最大金额。

现在考虑没有房子，所以max[0]=0

现在只考虑第一个房子，max[1] =在家里量1

现在首先考虑2房，

max[2] = {要么max[1]（意味着我们选择赃物房屋1）或（房屋2的金额+我抢劫的房屋的最大金额，直到房子位于我目前住宅的2个地方）} = {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个房屋中获得可以被抢劫的最大金额。

只有在以前有过一些练习和熟悉之后，DP问题才会成为头等大事，而这总是有所帮助。

来源

2016-09-17 02:03:30 brijs

基本上答案是f(n) = max(f(n-1), f(n-2) + arr[n])，你问为什么。

让我们假设这个数组和f(n)是函数。

当数组只有[9]，你的最大f(0)将arr[0]。

当数组为[9,1]，你的最大f(1)是max(arr[0], arr[1])。

当数组是[9,1,7]，如果选择7，你不能选择因此1f(n-2) + arr[n]。但是，如果您未选择7，则最大f(2)将与f(1)相同，即f(n-1)。

当阵列是[9,1,7,9]，则需要降二者1 & 7和选择9,9 f(n) = max(f(n-1), f(n-2)+arr[n])方程满足这种情况下。

来源

2017-05-20 23:12:22 Aaron

Leetcode房子劫匪

回答

相关问题