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

求职网站网页设计网站制作策划

求职网站网页设计,网站制作策划,很久以前做相册mv的网站,青州住房建设局网站打家劫舍 题解1 DP1题解2 DP2 !经典DP! 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果 两间相邻的房屋在同一晚上被小偷闯入…

打家劫舍

    • 题解1 DP1
    • 题解2 DP2

!经典DP!
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果 两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

示例 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

动态规划的的四个解题步骤是:

  1. 定义子问题: 总问题:抢N个房子 – > 子问题:抢 K个房子

  2. 写出子问题的递推关系:第k个房子要么被抢要么不被抢:F(k) = max(F(k-1), nums[k] + F(k-2))
    (只与前两个房子的最大金额有关——空间优化,N长数组变成2个变量)在这里插入图片描述

  3. 确定 DP 数组的计算顺序
    动态规划有两种计算顺序,一种是自顶向下的、使用备忘录的递归方法,一种是自底向上的、使用 dp 数组的循环方法。不过在普通的动态规划题目中,99% 的情况我们都不需要用到备忘录方法,所以我们最好坚持用自底向上的 dp 数组
    DP 数组中的依赖关系都是向右指的,DP 数组的计算顺序就是从左向右。这样我们可以保证,计算一个子问题的时候,它所依赖的那些子问题已经计算出来了。
    在这里插入图片描述

  4. 空间优化(可选)

题解1 DP1

class Solution {
public:int rob(vector<int>& nums) {int s = nums.size();vector<int> dp(s+1, 0);dp[1] = nums[0];for(int i = 1; i < s; i++){dp[i+1] = max(dp[i], dp[i-1]+nums[i]);}return dp[s];}
};

在这里插入图片描述

题解2 DP2

class Solution {
public:int rob(vector<int>& nums) {int s = nums.size();if(1 == s) return nums[0];int first = nums[0];int sec = max(nums[0], nums[1]);for(int i = 2; i < s; i++){int tmp = sec;// sec是i-1的情况, first是i-2sec = max(first+nums[i], sec);first = tmp;}return sec;}
};

在这里插入图片描述

http://www.hrbkazy.com/news/24935.html

相关文章:

  • 兰州手机网站制作公司线上销售平台如何推广
  • 电子商务网站建设上海推广网络营销咨询热线
  • wordpress插件刷不出来陕西整站关键词自然排名优化
  • 独立网站与其他网站外包公司是正规公司吗
  • 广州购物网站开发网页开发公司
  • wordpress首页缓存seo千享科技
  • 兼容ie8的网站模板兰州网站seo诊断
  • 国外web设计网站nba湖人队最新消息
  • 苏州web网站建设最新域名解析
  • 济南行业网站开发域名停靠
  • 专业做网站建设公怎么建立信息网站平台
  • 专做畜牧招聘网站的seo建设招商
  • 广州商城建站绍兴seo公司
  • 黄埔免费网站建设百度互联网营销顾问
  • 网站的友情链接怎么做上海有名网站建站开发公司
  • 郑州知名网站建设公司排名如何做网络营销推广
  • 政府网站建设管理会议百度投诉中心24人工客服
  • 企业网站推广的方式常用的网络营销方法及效果
  • ai写作网站深圳seo招聘
  • 视频分销网站建设国内最新新闻
  • 不知情的情况下帮别人做网站他违法搜索引擎优化seo公司
  • 南召微网站开发网站如何做优化推广
  • 网络营销是什么社会的必然产物seo品牌
  • 网站招聘怎么做创建网站的流程
  • 数据来源于网站怎么做参考文献网络推广外包哪个公司做的比较好
  • 金华网站建设适合seo的网站
  • 做编程的网站有哪些内容网站服务器怎么搭建
  • html5彩票网站模板定制网站开发公司
  • 签约网站做PPT郑州企业网络推广外包
  • wordpress如何安装网站主题汕头seo外包机构