网站建设需求确认书,网站后天添加文章不显示,软文模板,ipv6改造 网站怎么做61. 题目
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动报警。
给定一个代表每个房屋存…1. 题目
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下能够偷窃到的最高金额。
示例 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 。来源力扣LeetCode 链接https://leetcode-cn.com/problems/house-robber 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 动态规划解题
相关题目 LeetCode 213. 打家劫舍 IIDP LeetCode 337. 打家劫舍 III记忆化递归
dp[i]dp[i]dp[i]表示经过i房间时可以获得的最大金额显然有 dp[0]nums[0];dp[1]max(nums[0],nums[1])dp[0] nums[0]; \quad dp[1] max(nums[0],nums[1])dp[0]nums[0];dp[1]max(nums[0],nums[1])对第 iii 个房间有两种选择
偷dp[i]dp[i−2]nums[i]dp[i] dp[i-2]nums[i]dp[i]dp[i−2]nums[i]不偷dp[i]dp[i−1]dp[i] dp[i-1]dp[i]dp[i−1]
取2种情况的大者作为经过i房间获得的最大金额 状态转移公式dp[i]max(dp[i−2]nums[i],dp[i−1])dp[i] max(dp[i-2]nums[i], \quad dp[i-1])dp[i]max(dp[i−2]nums[i],dp[i−1])
class Solution {
public:int rob(vectorint nums) {int n nums.size(), i;if(n 0)return 0;else if(n 1)return nums[0];else if(n 2)return max(nums[0],nums[1]);int dp[n] {0};dp[0] nums[0];dp[1] max(nums[0],nums[1]);for(i 2; i n; i){dp[i] max(dp[i-2]nums[i], dp[i-1]);}return dp[n-1];}
};观察到上面转态转移公式只跟前两个转态有关可以进行压缩节省空间
class Solution {
public:int rob(vectorint nums) {int n nums.size(), i;if(n 0)return 0;else if(n 1)return nums[0];else if(n 2)return max(nums[0],nums[1]);int dp_i, dp_i_2 nums[0], dp_i_1 max(nums[0],nums[1]);for(i 2; i n; i){dp_i max(dp_i_2nums[i], dp_i_1);dp_i_2 dp_i_1;dp_i_1 dp_i;}return dp_i;}
};
