百度网站提交入口网址,哈尔滨网络建站的公司,建设购物网站流程图,wordpress 获取用户id1. 题目链接#xff1a;213. 打家劫舍 II
2. 题目描述#xff1a; 你是一个专业的小偷#xff0c;计划偷窃沿街的房屋#xff0c;每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 #xff0c;这意味着第一个房屋和最后一个房屋是紧挨着的。同时#xff0c;相邻…1. 题目链接213. 打家劫舍 II
2. 题目描述 你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。 示例 1 输入nums [2,3,2]
输出3
解释你不能先偷窃 1 号房屋金额 2然后偷窃 3 号房屋金额 2, 因为他们是相邻的。示例 2 输入nums [1,2,3,1]
输出4
解释你可以先偷窃 1 号房屋金额 1然后偷窃 3 号房屋金额 3。偷窃到的最高金额 1 3 4 。示例 3 输入nums [1,2,3]
输出3提示 1 nums.length 1000 nums[i] 1000 3. 解法动态规划
3.1 算法思路
这个问题是一个环形问题但是我们可以将环形问题转化为两个单排的问题
偷第一个房屋时的最大金额x此时不能偷最后一个房子因此就是偷[0,n-2]区间
不偷第一个房屋时的最大金额y此时可以偷最后一个房子因此就是偷[1,n-1]区间的房子
两种情况的最大值就是最终的结果 3.2 C算法代码
class Solution {
public:int rob(vectorint nums) {// 获取数组长度int n nums.size();// 返回两种情况的最大值偷第一个房子和不偷第一个房子return max(nums[0] rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));}// 定义一个辅助函数用于计算从left到right范围内能偷到的最大金额int rob1(vectorint nums, int left, int right) {// 如果left大于right说明没有房屋可以偷返回0if (left right) return 0;// 获取数组长度int n nums.size();// 初始化动态规划数组f和gvectorint f(n);auto g f;// 将第一个房屋的金额赋值给f[left]f[left] nums[left];// 从left1开始遍历到right更新动态规划数组f和g的值for (int i left 1; i right; i) {f[i] g[i - 1] nums[i]; // 当前房屋的最大金额等于前一个房屋的最大金额加上当前房屋的金额g[i] max(f[i - 1], g[i - 1]); // 当前房屋的最大金额等于前一个房屋的最大金额和前前个房屋的最大金额中的较大值}// 返回right位置的最大金额即偷到的最大金额return max(f[right], g[right]);}
};
