北京朝阳区二手房出售,湖北seo推广,做网站的免费空间,多个域名 一个网站文章目录 前言一、题目分析二、算法原理1.状态表示2.状态转移方程3.初始化4.填表顺序5.返回值是什么 三、代码实现总结 前言
在本文章中#xff0c;我们将要详细介绍一下LeetcodeLCR 090. 打家劫舍 II。采用动态规划解决#xff0c;这是一道经典的多状态dp问题
一、题目分析… 文章目录 前言一、题目分析二、算法原理1.状态表示2.状态转移方程3.初始化4.填表顺序5.返回值是什么 三、代码实现总结 前言
在本文章中我们将要详细介绍一下LeetcodeLCR 090. 打家劫舍 II。采用动态规划解决这是一道经典的多状态dp问题
一、题目分析 计算小偷能偷到的最大金额数并且题目规定 .两个相邻的房屋不能被偷 .第一个房屋和最后一个房屋不能被偷 规定1比较好解决对于规定2我们采用分情况讨论的方法解决 .第一个房间偷第二个房间和最后一个不被偷在2n-2下标之间寻找最大金额再加上nums[0]. .第一个房间不被偷最后一个房间不确定在1n-1下标之间寻找最大金额 .二者取最大值就是题目所返回的值
二、算法原理
1.状态表示
列出dp表dp表中值的含义是什么 这可以细分为两个表因为经过该房间时不确定偷与不偷 ⭐️ .f[i]表示到达i房间时资金被偷 ⭐️.g[i]表示到达i房间时资金没有被偷
2.状态转移方程
根据最近一步划分问题 f[i]:i位置被偷那么根据题目规定i-1位置就不能被偷这不就正好是g[i-1],再加上i位置被偷的资金; g[i]:i位置没有被偷i-1位置我们不确定有没有被偷所以需要分为两种情况这两种情况取最大值 .i-1位置也没有被偷就是g[i-1] .i-1位置被偷了就是f[i-1] 结论 f[i]g[i-1]nums[i]; g[i]max(g[i-1],f[i-1])
3.初始化
保证填表不越界 f[1]需要g[0]的值g[1]需要g[0]和f[0]的值, 所以需要初始化g[0]和f[0]. 不用开辟额外的空间这道题目的初始化很简单。 注意数组的下标和边界条件
4.填表顺序
两个表一起填从左往右
5.返回值是什么
max(f[n-1],g[n-1]);
三、代码实现
class Solution {
public:int massage(vectorint nums,int left,int right) {if(leftright){return 0;}//建表int nnums.size();int f[n];int g[n];//初始化for(int i0;in;i){f[i]g[i]0;}f[left]nums[left];g[0]0;//填表for(int ileft;iright;i){f[i]g[i-1]nums[i];g[i]max(g[i-1],f[i-1]);}//返回值return max(f[right],g[right]);}int rob(vectorint nums) {int nnums.size();//下标int ret1massage(nums,2,n-2)nums[0];int ret2massage(nums,1,n-1);return max(ret1,ret2);}
};总结
以上就是我们对LeetcodeLCR 090. 打家劫舍 II(leetcode)详细介绍希望对大家的学习有所帮助仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~
