打家劫舍 IV

题目描述

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。

小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。

另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。

返回小偷的 最小 窃取能力。

样例

样例输入

nums = [2,3,5,9], k = 2
nums = [2,7,9,3,1], k = 2

样例输出

5
2

提示

• $1<=nums.length<=10^5$
• $1<=nums[i]<=10^9$
• $1<=k<=(nums.length+1)/2$

思路

这题目刚开始根本想不到使用二分+动态规划。
看的题解

代码实现

class Solution {int[] nums;int k;public int minCapability(int[] nums, int k) {this.nums = nums;this.k = k;int r = 0;for(var n : nums)if(r < n)r = n;int l = 1; while(l <= r){int mid = (l + r) >> 1;if(check(mid)) r = mid - 1;else l = mid + 1;}return l;}private boolean check(int num){int dp0 = 0, dp1 = 0;for(var n : nums){if(n > num) dp0 = dp1;else{int tmp = dp1;dp1 = Math.max(dp1, dp0 + 1);dp0 = tmp;}}return dp1 >= k;}
}

获得分数的方法数

题目描述

考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有 counti 道，每道题目对应 marksi 分。

返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 109 +7 取余。

注意，同类型题目无法区分。

比如说，如果有 3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。

样例

样例输入

target = 6, types = [[6,1],[3,2],[2,3]]
target = 5, types = [[50,1],[50,2],[50,5]]
target = 18, types = [[6,1],[3,2],[2,3]]

样例输出

7
4
1

提示

• 1 <= target <= 1000
• n == types.length
• 1 <= n <= 50
• types[i].length == 2
• 1 <= counti, marksi <= 50

思路

分组背包模版题，但还是初次接触，借鉴了一下

代码实现

class Solution {public int waysToReachTarget(int target, int[][] types) {int MOD = (int)1e9 + 7;long[] dp = new long[target + 1];dp[0] = 1;for(int[] type : types){for(int i = target; i > 0; i--){for(int j = 1; j <= Math.min(type[0], i / type[1]); j++){dp[i] += dp[i - type[1] * j];}dp[i] %= MOD;}}return (int)dp[target];}
}