Leetcode2560. 打家劫舍 IV

Every day a Leetcode

题目来源：2560. 打家劫舍 IV

解法1：二分答案 + 动态规划

给定数组 nums，从中选择一个长度至少为 k 的子序列 A，要求 A 中没有任何元素在 nums 中是相邻的。

最小化 max⁡(A)。

看到「最大化最小值」或者「最小化最大值」就要想到二分答案，这是一个固定的套路。

对于本题，「偷走的最大金额」越小，能偷的房子就越少，反之越多。

一般地，二分的值越小，越不能/能满足要求；二分的值越大，越能/不能满足要求。有单调性的保证，就可以二分答案了。

把二分中点 mid 记作 mx，定义 dp[i] 表示从 nums[0] 到 nums[i] 中偷金额不超过 mx 的房屋，最多能偷多少间房屋。如果 dp[n−1]≥k 则表示答案至多为 mx，否则表示答案必须超过 mx。

用「选或不选」来分类讨论：

不选 nums[i]：dp[i]=dp[i−1]；
选 nums[i]，前提是 nums[i]≤mx：dp[i]=dp[i−2]+1。

这两取最大值，即：dp[i]=max(dp[i−1],dp[i−2]+1)。

代码：

/** @lc app=leetcode.cn id=2560 lang=cpp** [2560] 打家劫舍 IV*/// @lc code=start// 二分答案 + 动态规划class Solution
{
public:int minCapability(vector<int> &nums, int k){int n = nums.size();int left = *min_element(nums.begin(), nums.end());int right = *max_element(nums.begin(), nums.end());// mx 是二分猜测的窃取能力auto check = [&](int mx, int k) -> bool{// dp[i]: 从 nums[0, i] 中偷金额不超过 mx 的房屋，最多能偷多少间房屋vector<long long> dp(n, 0);// 初始化dp[0] = nums[0] <= mx ? 1 : 0;if (dp[0] || nums[1] <= mx)dp[1] = 1;// 状态转移for (int i = 2; i < n; i++){if (nums[i] > mx)dp[i] = dp[i - 1];elsedp[i] = max(dp[i - 1], dp[i - 2] + 1);}return dp[n - 1] >= k;};while (left < right){int mid = left + (right - left) / 2;if (check(mid, k))right = mid;elseleft = mid + 1;}return left;}
};
// @lc code=end

结果：

在这里插入图片描述

复杂度分析：

时间复杂度：O(nlogU)，其中 n 为数组 nums 的长度，U=max(nums)。

空间复杂度：O(n)，其中 n 为数组 nums 的长度。

解法2：二分答案 + 贪心

也可以用贪心做。

考虑到只需要计算个数，在从左到右遍历的情况下只要当前房子可以偷，就立刻偷。

严格证明如下：

在这里插入图片描述

代码：

// 二分答案 + 贪心class Solution
{
public:int minCapability(vector<int> &nums, int k){int n = nums.size();int left = *min_element(nums.begin(), nums.end());int right = *max_element(nums.begin(), nums.end());// mx 是二分猜测的窃取能力auto check = [&](int mx, int k) -> bool{int count = 0;for (int i = 0; i < n; i++)if (nums[i] <= mx){count++;i++; // 跳过下一间房子}return count >= k;};while (left < right){int mid = left + (right - left) / 2;if (check(mid, k))right = mid;elseleft = mid + 1;}return left;}
};