当前位置: 首页 > news >正文

石家庄网站建设公司怎么样搜索指数查询

石家庄网站建设公司怎么样,搜索指数查询,在家做兼职哪个网站靠谱,做旅游攻略什么网站最好动态规划里面一部题目打家劫舍是一类经典的算法题目之一,他有各种各样的变式,这一篇文章和大家分享一下打家劫舍最基础的一道题目,掌握这一道题目,为下一道题目打下基础。我们直接进入正题。一.题目大家如果刚接触这样的题目&…

动态规划里面一部题目打家劫舍是一类经典的算法题目之一,他有各种各样的变式,这一篇文章和大家分享一下打家劫舍最基础的一道题目,掌握这一道题目,为下一道题目打下基础。我们直接进入正题。

一.题目

大家如果刚接触这样的题目,会有点困惑,当前的状态我是偷还是不偷呢?

仔细一想,当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。

所以这里就更感觉到,当前状态和前面状态会有一种依赖关系,那么这种依赖关系都是动规的递推公式。

当然以上是大概思路,打家劫舍是dp解决的经典问题,接下来我们来动规五部曲分析如下:

二.动态规划五部曲

  1. 确定dp数组(dp table)以及下标的含义

dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]

2.确定递推公式

决定dp[i]的因素就是第i房间偷还是不偷。

如果偷第i房间,那么dp[i] = dp[i - 2] + nums[i] ,即:第i-1房一定是不考虑的,找出 下标i-2(包括i-2)以内的房屋,最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。

如果不偷第i房间,那么dp[i] = dp[i - 1],即考 虑i-1房,(注意这里是考虑,并不是一定要偷i-1房,这是很多人容易混淆的点

然后dp[i]取最大值,即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

3.dp数组如何初始化

从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出,递推公式的基础就是dp[0] 和 dp[1]

从dp[i]的定义上来讲,dp[0] 一定是 nums[0],dp[1]就是nums[0]和nums[1]的最大值即:dp[1] = max(nums[0], nums[1]);

代码如下:

vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

4.确定遍历顺序

dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的,那么一定是从前到后遍历!

代码如下:

for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}

5.举例推导dp数组

以示例二,输入[2,7,9,3,1]为例。

红框dp[nums.size() - 1]为结果。

以上分析完毕,C++代码如下:

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];vector<int> dp(nums.size());dp[0] = nums[0];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];}
};

Java代码如下:

// 动态规划
class Solution {public int rob(int[] nums) {if (nums == null || nums.length == 0) return 0;if (nums.length == 1) return nums[0];int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Math.max(dp[0], nums[1]);for (int i = 2; i < nums.length; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[nums.length - 1];}
}

总结:

打家劫舍是DP解决的经典题目,这道题也是打家劫舍入门级题目,后面我们还会变种方式来打劫的。

做算法题最重要的就是坚持。大家加油!

http://www.zhongyajixie.com/news/21384.html

相关文章:

  • 珠海一元夺宝网站建设新网站怎么做推广
  • 荥阳做网站推广爱站seo查询软件
  • 网站建设费用会计处理济南头条新闻热点
  • 中资建筑信息平台seo培训中心
  • 政府办公室网站建设google浏览器下载
  • 做网站最简单的工具网上培训课程平台
  • 青海门户网站建设google chrome浏览器
  • 软件开发app开发定制外包11seo西安
  • 简单网页的设计过程郑州seo网络营销
  • asp网站怎么做301定向百度系优化
  • 专业的网站设计网络足球积分排行榜最新
  • curl 下载网站图片刚刚中国出啥大事了
  • 垂直性门户网站有哪些发稿
  • 家具flash网站模板下载网上代写文章一般多少钱
  • html css 网站模板游戏代理
  • 编程自己做网站广东seo快速排名
  • 中国十大做网站公司百度官方网址
  • 微信网站开发多少钱微信scrm系统
  • 泉州网站建设哪家公司好南宁网站seo外包
  • 滁州市琅琊区规划建设局网站百度网盘下载
  • 新乡网站优化谁能给我个网址
  • 怎么做网站出肉狗抖音广告推广怎么收费
  • 德州市建设街小学网站网站的营销推广方案
  • 网站前端设计要做什么的谷歌排名推广
  • 购买手表的网站网络营销策划与创意
  • 做鱼网站的域名长春百度seo排名
  • 资源网站很难做网站长尾关键词排名软件
  • 真正免费网站申请全国疫情防控最新数据
  • 网站做百度百科百度地图关键词优化
  • php企业网站管理系统拉新充场app推广平台