成绩查询网站开发,土特产网站模板 织梦,offic做网站的软件,python版 wordpress第十二章 打家劫舍题目理解步骤dp数组递推公式初始化遍历顺序 代码 打家劫舍II题目理解步骤递推公式初始化遍历顺序 代码 打家劫舍
力扣链接
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋… 第十二章 打家劫舍题目理解步骤dp数组递推公式初始化遍历顺序 代码 打家劫舍II题目理解步骤递推公式初始化遍历顺序 代码 打家劫舍
力扣链接
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额 示例 1 输入[1,2,3,1] 输出4 解释偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3) 偷窃到的最高金额 1 3 4 示例 2 输入[2,7,9,3,1] 输出12 解释偷窃 1 号房屋 (金额 2), 偷窃 3 号房屋 (金额 9)接着偷窃 5 号房屋 (金额 1) 偷窃到的最高金额 2 9 1 12 提示 1 nums.length 100 0 nums[i] 400
题目理解
不能在相邻的房屋进行偷窃, 还要求一夜之间能够偷窃的最高金额 那小偷到这个房屋偷还是不偷?
⇒ 偷窃到第 i 个房屋的最大金额 取决于上一次偷窃的是哪个房屋(取决于 第 i -1 个房屋的偷取状态 和 第 i - 2 个房屋的偷取状态) ⇒ 我们可以采用 动态规划的思想
步骤
dp数组
影响因素只有一个, 上一次偷窃的是哪个房屋⇒ dp数组用 一维 的就可以 dp[i] — — [0, i]房屋所得到的最大金额
递推公式
偷窃到第 i 个房屋, 我们能够进行的操作有哪一些:
所相邻的房屋并没有偷窃, 那我们这个房屋就能进行偷窃 — — dp[i-2] nums[i]所相邻的房屋已经偷窃了, 那我们这个房屋就不能进行偷窃 — — dp[i-1]
最后的结果, 是取两者的最大值⇒ dp[i] max(dp[i-1], dp[i-2] nums[i])
初始化
根据递归公式, 我们发现最基础的是 dp[0] 和 dp[1] dp[0] — — 第一个房屋所能偷窃的最大价值, 那肯定是偷了它 — — dp[0] nums[0] dp[1] — — 前两个房屋所能偷窃的最大价值, 那肯定是偷它们之间的最大价值的那个 — — dp[1] max(nums[0], nums[1])
遍历顺序
根据递归公式, 第 i 天的状态是由前面决定的 ⇒ 那么是 由前到后的遍历方向
代码
class Solution {
public:int rob(vectorint nums) {// dp[i] -- -- 区间[0, i]的最大价值vectorint dp(nums.size() 1, 0);dp[0] nums[0];if(nums.size() 1)dp[1] max(nums[0], nums[1]);for(int i 2; i nums.size(); i){dp[i] max(dp[i - 2] nums[i], dp[i - 1]);}return dp[nums.size() - 1];}
};打家劫舍II
力扣链接
你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额 示例 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 100 0 nums[i] 1000
题目理解
这个题目跟上面的很相似, 但是有一个点是不同的: 上面是个线性的, 这个题目是圆形的
那么, 我们能不能用上一个题目的解法来解决这个题目呢? 首先, 先将圆形转化为线性的
在区间[0, i]中, 我们发现:
0为开端, 那么 i 是不能是结尾 (最大是 i - 1结尾)1为开端, 那么 i 是能是结尾的 ⇒ 那么我们就可以划分为两个区间: [0, i - 1] 和 [1, i]
步骤
递推公式
偷窃到第 i 个房屋, 我们能够进行的操作有哪一些:
所相邻的房屋并没有偷窃, 那我们这个房屋就能进行偷窃 — — dp[i-2] nums[i]所相邻的房屋已经偷窃了, 那我们这个房屋就不能进行偷窃 — — dp[i-1]
最后的结果, 是取两者的最大值⇒ dp[i] max(dp[i-1], dp[i-2] nums[i])
初始化 区间为[0, n - 1]: dp[0] nums[0] dp[1] max(nums[0], nums[1]) 区间为[1, n]: dp[1] nums[1] dp[2] max(nums[1], nums[2])
遍历顺序
根据递归公式, 第 i 天的状态是由前面决定的 ⇒ 那么是 由前到后的遍历方向
代码
class Solution {
public:int rob(vectorint nums) {// 将环形问题拆分为线性问题// 将区间[0, n] 拆分为 包含第一个节点,不包含最后一个节点 和 不包含第一个节点,包含最后一个节点// 即将区间[0, n] 拆分为 [0, n-1] 和 [1, n] 两个区间// 最后返回两个区间最大值的最大值if(nums.size() 1) return nums[0];if(nums.size() 2) return max(nums[0], nums[1]);vectorint dp(nums.size() 1, 0);dp[0] nums[0];dp[1] max(nums[0], nums[1]);for(int i 2; i nums.size() - 1; i){dp[i] max(dp[i - 2] nums[i], dp[i - 1]);}int max1 dp[nums.size() - 2];dp[1] nums[1];dp[2] max(nums[1], nums[2]);for(int i 3; i nums.size(); i){dp[i] max(dp[i - 2] nums[i], dp[i - 1]);}int max2 dp[nums.size() - 1];return max(max1, max2);}
};连伟人的一生都充满了那么大的艰辛一个平凡的人吃点苦又算得了什么呢 — — 路遥
