成都网站建设与推广,网站建设1001网站建设,成都网站建设中心,大良网站制作1.打家劫舍II 题目链接#xff1a; 213. 打家劫舍 II - 力扣#xff08;LeetCode#xff09;https://leetcode.cn/problems/house-robber-ii/ 2. 题目解析 通过分类讨论#xff0c;将环形问题转换为两个线性的“打家劫舍|” 当偷第一个位置的时候#xff0c;rob1在#…1.打家劫舍II 题目链接 213. 打家劫舍 II - 力扣LeetCodehttps://leetcode.cn/problems/house-robber-ii/ 2. 题目解析 通过分类讨论将环形问题转换为两个线性的“打家劫舍|” 当偷第一个位置的时候rob1在2n-2的区间进行一次打家劫舍|当不偷第一个位置的时候rob1在1,n-1的区间进行一次打家劫舍| 3. 算法原理 状态表示以某一个位置为结尾或者以某一个位置为起点 dp[i]表示偷到i位置的时候此时的最大金额分两种情况 1.f[i]表示偷到i位置的时候当前位置nums[i]必偷此时的最大金额 2.g[i]表示偷到i位置的时候当前位置nums[i]不偷此时的最大金额 2. 状态转移方程 根据最近的一步来划分问题 到达dp[i][j]有两种情况 1. f[i]g[i-1] nums[i] 2. g[i]a. 当选择i-1的位置时f[i-1] b.当不选择i-1的位置时g[i-1] g[i]max(f[i-1],g[i-1]) 3. 初始化 把dp表填满不越界让后面的填表可以顺利进行 本题初始化为f[0]nums[0] g[0]0 4. 填表顺序 本题的填表顺序是从左往右两个表一起填 5. 返回值 题目要求 状态表示 偷到最后一个位置分为两种情况偷和不偷 本题的返回值是max(f[n-1],g[n-1]) 4.代码 动态规划的固定四步骤1. 创建一个dp表 2. 在填表之前初始化 3. 填表填表方法状态转移方程 4. 确定返回值 class Solution {
public:int rob(vectorint nums) {int nnums.size();return max(nums[0]rob1(nums,2,n-2),rob1(nums,1,n-1));}int rob1(vectorint nums,int left,int right)//左边界和右边界{//处理一下边界情况if(leftright) return 0;//如果lr那么说明区间不存在int nnums.size();vectorintf(n);//开辟两个dp表auto gf;//将l到r这段区间的值初始化f[left]nums[left];//从l1的位置开始填表for(int ileft1;iright;i){f[i]g[i-1]nums[i];g[i]max(f[i-1],g[i-1]);}return max(f[right],g[right]);}
}; 完结撒花~
