Leetcode家劫匪问题

Question

我正在尝试解决LeetCode上的House Robber问题（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];
   }

但我就是无法理解这个逻辑。请帮我理清逻辑，以及如何解决类似的问题？

- srip

Answer 1

基本上答案是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] )满足这种情况。

- aerin

Answer 2

假设我将每个房子的金额存储在 house[k] 中。

现假设我将前 k 个房屋(仅限前 k 个)中能够掠夺到最大金额存储在 max[k] 中。

现在考虑没有房子，因此 max[0]=0。

现在只考虑第一间房子，max[1]=第一间房子的金额。

现在考虑前两个房子， max[2]={要么是max[1]（表示我们选择掠夺第一间房子），要么是（第二间房子的金额+直到我的当前房子位于其前面两个位置为止我已经掠夺到的最大金额）}={max(max[1],house[2]+max[0])} 同样地，对于前三个房子，max[3]=max(max[2],house[3]+max[1]) 观察这一趋势，可以得出公式：max[k]=max(max[k-1],house[k]+max[k-2])。计算这个值时一直进行下去，直到没有更多房子可掠夺，我们就可以得到从这些前 n 个房子中最多可以掠夺的金额。

只有当您有一定的练习和熟悉度时，DP问题才会变得容易起来。这种熟练度是十分有帮助的。

- brijs

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))

这也可以很容易地记忆，如果你想提高效率。

- SeasonalShot