Leetcode 入室抢劫犯

我正在尝试入室抢劫者 https://leetcode.com/problems/house-robber/leetcode 上的问题（dp 问题）。 来自一位 GTX 用户的解决方案看起来简单而优雅。

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

但我就是无法理解其中的逻辑。请帮助我理解逻辑以及如何解决这样的问题？

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

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

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

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

当数组为[9,1,7]，如果您选择7, you can't select 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] )方程满足这种情况。