algorithm - Leetcode 房子强盗

Question

我正在尝试 House Robber 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

基本上答案是 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，则不能 strong> 选择 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] ) 方程满足这种情况。