一个方法团灭 LeetCode 打家劫舍问题 :: labuladong的算法小抄

[labuladong]

文章链接点这里：一个方法团灭 LeetCode 打家劫舍问题

评论礼仪 见这里，违者直接拉黑。

[fzfzlfz]

学到了！！

[cheng-miao]

学到了

[sadadasad]

感谢东哥分享的文章，层次鲜明，难度递进，学到了很多东西。
关于打家劫舍2，个人觉得有一个更好理解的方案。因为不能同时抢第一间房子和最后一间房子，所以可以将问题看作是抢排成一排的前n-1间房子或是后n-1间房子的最值，即转化为打家劫舍1的两种情况，也就是东哥实际给出的解题代码。在东哥说明提出的三种情况与实际的解题代码存在冲突。而且只取后面两种情况的方式是错误的，力扣原题给出的案例nums = [2,3,2]，取到的最值就在于第一间和最后一间都不抢的情况。

[LeeHaruYa]

滴滴滴打卡

[Velliy]

打家劫舍1 这个自顶向下的dp也不错的，也好理解，比递归简单点。
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(dp[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}

[hepytobecool]

抢房子

[mhli971]

最后一个tree的很有启发性，对于tree structure，可以直接通过天然的recursion来保证每个node只计算一次，并且每个node 记录抢或不抢的二元组也很聪明，学习了

[bruceeewong]

20221229 打卡

[Jianjiaze]

第三道题的两种解法都很巧妙，可以加深对重叠子问题的理解，获益匪浅

[mlu12321]

为什么house robber的dp[i]定义是从该位置start的最大值，而LIS是在该位置结束的最大值呢~ 我能理解为什么这样是行得通的，但在找思路的时候自己就想不到这个解法

[hjw6160602]

感谢东哥！ 来一个打家劫舍III的 Swift版本：

[hjw6160602]

func rob(_ root: TreeNode?) -> Int {
        let res = dp(root)
        return max(res[0], res[1])
    }

    /* 返回一个大小为 2 的数组 arr
       arr[0] 表示不抢 root 的话，得到的最大钱数
       arr[1] 表示抢 root 的话，得到的最大钱数 */
    private func dp(_ root: TreeNode?) -> [Int] {
        guard let node = root else {
            return [0, 0]
        }
        let left = dp(node.left)
        let right = dp(node.right)
        // 抢, 下家就不能抢了
        let rob = node.val + left[0] + right[0]
        // 不抢，下家可抢可不抢，取决于收益大小
        let notRob = max(left[0], left[1]) + max(right[0], right[1])
         
        return [notRob, rob]
    }

[86driver]

ddd

[laoyoutiao237]

第三题来个c++版

    int rob(TreeNode* root) {
        auto ans = rob_aux(root);
        return max(ans.first, ans.second);
    }

    pair<int, int> rob_aux(TreeNode* root){
        if(root == nullptr) return {0, 0};
        auto le = rob_aux(root->left), ri = rob_aux(root->right);
        return {root->val + le.second + ri.second, max(le.first, le.second) + max(ri.first, ri.second)};
    }

[CarlLy7]

打卡

[jasonren0403]

抢房子