【力扣一刷】代码随想录day48（动态规划part9 - 打家劫舍专题：198.打家劫舍、213.打家劫舍II 、337.打家劫舍III）_C/C++

【198. 打家劫舍】中等题（偏简单）

class solution {
    public int rob(int[] nums) {
        // dp[i]:从0到i间房子中一夜之内能偷窃到的最高金额
        // 偷：dp[i] = dp[i-2] + nums[i]
        // 不偷：dp[i] = dp[i-1] (最高金额还是和从0到i-1间房子中一夜之内能偷窃到的最高金额一致)

        if (nums.length < 2) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0]; // 只有一间房，那肯定偷
        dp[1] = math.max(nums[0], nums[1]); // 有两间房（必定相邻），只能选其中最高金额的偷

        for (int i = 2; i < dp.length; i++){
            dp[i] = math.max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[nums.length-1];
    }
}

时间复杂度：o(n)，n是nums数组的长度，for循环遍历了一次
空间复杂度：o(n)，dp数组的长度等于nums数组的长度

【优化】空间复杂度o(n) -> o(1)

class solution {
    public int rob(int[] nums) {
        // z:从0到i间房子中一夜之内能偷窃到的最高金额
        // 偷：z = x + nums[i]
        // 不偷：z = y (最高金额还是和从0到i-1间房子中一夜之内能偷窃到的最高金额一致)

        if (nums.length < 2) return nums[0];
        int x = nums[0];
        int y = math.max(nums[0], nums[1]);
        int z = 0; 
        for (int i = 2; i < nums.length; i++){
            z = math.max(y, x + nums[i]);
            x = y;
            y = z;
        }
        return y;
    }
}

时间复杂度：o(n)，n是nums数组的长度，for循环遍历了一次
空间复杂度：o(1)，无论输入的nums数组多长，都只用三个变量就足够

【213. 打家劫舍 ii】中等题（思路要理清）

class solution {
    public int rob(int[] nums) {
        if (nums.length < 2) return nums[0];
        int dp1 = robsimple(nums, 0, nums.length-2); // 不偷尾元素
        int dp2 = robsimple(nums, 1, nums.length-1); // 不偷头元素
        return math.max(dp1, dp2);
        
    }
    // 根据索引求nums某区间内的最高金额
    public int robsimple(int[] nums, int start, int end){
        if (end == start) return nums[start];

        int x = nums[start]; // 只有一间房，那肯定偷
        int y = math.max(nums[start], nums[start+1]); // 有两间房（必定相邻），只能选其中最高金额的偷
        for (int i = start+2; i < end+1; i++){
            int z = math.max(y, x + nums[i]);
            x = y;
            y = z;
        }
        return y;
    }
}

时间复杂度：o(n)，n是nums数组的长度
空间复杂度：o(1)，无论输入的nums数组多长，都只用三个变量就足够

【337. 打家劫舍 iii】中等题（按照198题的思路不难）

class solution {
    int sons = 0;
    public int rob(treenode root) {
        return robdfs(root);
    }
    // 递归 - 后序遍历（左右中）
    public int robdfs(treenode root){
        // 递归的终止条件
        if (root == null) {
            sons = 0; // 空节点的所有孩子最高金额的和为0
            return 0; // 空节点的最高金额也为0
        }

        // 规则：
        // -不偷：偷所有儿子的 = 最高金额选择1
        // -偷：偷自己的 + 所有孙子的 = 最高金额选择2
        int grandsons = 0;
        int leftson = robdfs(root.left); // 获取左儿子的最高金额
        grandsons += sons; // 左儿子的儿子是孙子的一部分
        int rightson = robdfs(root.right); // 获取右儿子的最高金额
        grandsons += sons; // 右儿子的而是是孙子的另一部分
        sons = leftson + rightson; // 左儿子的最高金额 + 右儿子的最高金额 = 所有儿子的最高金额的和
        return math.max(sons, grandsons + root.val); // 选偷和不偷的最高金额
    }
}