There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he **refuses to steal from adjacent homes**.

The **capability** of the robber is the maximum amount of money he steals from one house of all the houses he robbed.

You are given an integer array `nums`

representing how much money is stashed in each house. More formally, the `i`

house from the left has ^{th}`nums[i]`

dollars.

You are also given an integer `k`

, representing the **minimum** number of houses the robber will steal from. It is always possible to steal at least `k`

houses.

Return *the minimum *capability of the robber out of all the possible ways to steal at least

`k`

houses.**Example 1:**

Input:nums = [2,3,5,9], k = 2Output:5Explanation:There are three ways to rob at least 2 houses: - Rob the houses at indices 0 and 2. Capability is max(nums[0], nums[2]) = 5. - Rob the houses at indices 0 and 3. Capability is max(nums[0], nums[3]) = 9. - Rob the houses at indices 1 and 3. Capability is max(nums[1], nums[3]) = 9. Therefore, we return min(5, 9, 9) = 5.

**Example 2:**

Input:nums = [2,7,9,3,1], k = 2Output:2Explanation:There are 7 ways to rob the houses. The way which leads to minimum capability is to rob the house at index 0 and 4. Return max(nums[0], nums[4]) = 2.

**Constraints:**

`1 <= nums.length <= 10`

^{5}`1 <= nums[i] <= 10`

^{9}`1 <= k <= (nums.length + 1)/2`

**Solution 1: Binary Search + DP**

It’s easy to see that higher capability means more houses we can rob. Thus this can be formulate as a binary search algorithm e.g. find the minimum C s.t. we can rob at least k houses.

Then we can use dp(i) to calculate maximum houses we can rob if starting from the i’th house.

dp(i) = max(1 + dp(i + 2) if nums[i] <= C else 0, dp(i + 1))

Time complexity: O(n log m)

Space complexity: O(n)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua class Solution { public: int minCapability(vector<int>& nums, int k) { int l = 0; int r = *max_element(begin(nums), end(nums)) + 1; vector<int> cache(nums.size(), -1); function<int(int, int)> rob = [&](int m, int i) -> int { if (i >= nums.size()) return 0; if (cache[i] >= 0) return cache[i]; if (nums[i] > m) return rob(m, i + 1); return cache[i] = max(1 + rob(m, i + 2), rob(m, i + 1)); }; while (l < r) { int m = l + (r - l) / 2; fill(begin(cache), end(cache), -1); if (rob(m, 0) >= k) r = m; else l = m + 1; } return l; } }; |

**Solution 2: Binary Search + Greedy**

From: dp(i) = max(1 + dp(i + 2) if nums[i] <= C else 0, dp(i + 1)) we can see that if we can pick the i-th one, it will be the same or better if we skip and start from dp(i + 1). Thus we can convert this from DP to greedy. As long as we can pick the current one, we pick it first.

Time complexity: O(n log m)

Space complexity: O(1)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua class Solution { public: int minCapability(vector<int>& nums, int k) { int l = 0; int r = *max_element(begin(nums), end(nums)) + 1; auto rob = [&](int m) -> int { int ans = 0; for (int i = 0; i < nums.size(); ++i) if (nums[i] <= m) { ++ans; ++i; } return ans; }; while (l < r) { int m = l + (r - l) / 2; if (rob(m) >= k) r = m; else l = m + 1; } return l; } }; |