Leetcode住宅劫匪

Question

我在leet代码上尝试屋贼问题(dp问题)。来自其中一个用户GYX的解决方案看起来简单而优雅。

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

但我就是想不通逻辑。请帮助我的逻辑，并如何处理这样的问题？

Answer 1

假设我把这笔钱存储在house[k]的kth房子里。

假设现在我将尽可能多的钱存储在max[k]的第一个k个房屋(和第一个k)中。

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

现在只考虑第一栋房子，max[1]=房屋1中的数量

现在考虑到前两栋房子，

max[2]={max[1](意味着我们选择洗劫房屋1)或(房屋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问题才会让你头脑发热，这总是有帮助的。

Answer 2

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

让我们假设这个数组arr = [9,1,7,9]和f(n)是函数。

当数组仅为[9]，时，则最大f(0)为arr[0]。

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

当数组为[9,1,7]，时，如果选择7，则不能选择1，因此选择f(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] )方程满足这种情况。

Answer 3

看看这个简单的递归代码。可视化一个在DP中解决的问题乍一看是困难的。首先，您应该从低性能递归代码一直到这一点。下面是不同版本的代码：

p = [0, 1, 2, 3, 1, 2, 3, 1, 2, 5, 8, 2]
def R(i):
    if i == 1 or i == 2:
        return i
    else:
        return max(p[i] + R(i - 2), R(i - 1))

print(R(11))

这也是很容易回忆录，如果你想提高效率。