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 ith house from the left has 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 = 2
Output: 5
Explanation:
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 = 2
Output: 2
Explanation: 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
這題給我們一個一維正整數陣列 nums，
代表一條街上每間房子內含的錢。
今天有一個小偷非常的有原則，
明明可以全部偷光光，但是堅守著只要偷了這棟，下一棟就不偷的原則。
並且小偷最少可以偷 K間房子。
試問在小偷的行竊行為底下，
被小偷偷走單棟最高的錢為多少？
好拗口，簡單來說就是能不能找到一個組合內含 K個房子？
並且最小化這 K個房子中錢的最大值？
我看到題目腦中想：
我哪知道小偷要偷哪幾棟？而且最小化是什麼鬼？
通常不知道要偷哪幾棟，又有連續關係的就是 DP。
最小化單棟的錢，就是二分搜尋指定的錢數目，
看看這條街（nums）與條件 K 能不能幫我們達成？
我們把單間房子內含錢的最大值設定為 mid，下去二分搜尋，
當單間房子的錢超過 mid 就不偷，並用 DP紀錄偷與不偷的選擇，
在當下總共偷了幾間？
DP C++程式碼：
