网站建设销售技巧和话术,太原网站开发团队,网站按钮确定后图片怎么做,住房与城乡建设网上办事大厅打家劫舍 IV
题目描述
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统#xff0c;所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大…打家劫舍 IV
题目描述
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上从左起第 i 间房屋中放有 nums[i] 美元。
另给你一个整数 k 表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。
返回小偷的 最小 窃取能力。
样例
样例输入 nums [2,3,5,9], k 2 nums [2,7,9,3,1], k 2 样例输出 5 2 提示
1nums.length1051 nums.length 10^51nums.length1051nums[i]1091 nums[i] 10^91nums[i]1091k(nums.length1)/21 k (nums.length 1)/21k(nums.length1)/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 1000n types.length1 n 50types[i].length 21 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];}
}
