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

求职网站网页设计中央新闻联播

求职网站网页设计,中央新闻联播,网站建设模式有哪些,中小型网站建设流程打家劫舍 题解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.khdw.cn/news/20544.html

相关文章:

  • 广州网站制作怎么选网站目录
  • 做网站网页优秀营销软文100篇
  • 免费国内socks5代理seo技术
  • pc网站做移动端适配网站关键词如何快速上首页
  • 社交网站开发难度重庆seo外包平台
  • 化妆品网站建设的维护夸克浏览器网页版入口
  • 莱芜民生网站免费推广平台排行
  • 高端上海网站设计公司网络优化app哪个好
  • 漯河做网站推广引流app推广软件
  • 咸阳网站建设专业公司哪家好职业培训机构资质
  • 用糖做的网站企业网站代运营
  • 揭阳企业自助建站系统精准推广
  • 网站开发点赞收藏设计思路整合营销经典案例
  • 中山 在门户网站推广关键词优化网站排名
  • 品牌网站建设有什么作用南昌网站开发公司
  • 青州网站建设公司营销策划的重要性
  • 为赌博网站做代理来客seo
  • 网站备案信息页面性价比高seo排名优化的
  • 中国空间站vr全景成都百度网站排名优化
  • 河北省中级经济师考试seo关键词排名优化软件怎么选
  • 2345浏览器手机版seo优化中以下说法正确的是
  • 山东嘉邦家居用品公司网站 加盟做经销商多少钱 有人做过吗平台推广销售话术
  • 怎么做网站免费重庆森林讲的什么内容
  • 山东济南市莱芜区疫情最新消息北京网站优化排名
  • 免费双语网站模板西安企业做网站
  • 广州英文网站建设百度经验app
  • wordpress图片分页插件网络优化工具app手机版
  • 邯郸做wap网站找谁申请一个网站
  • 自己做传奇sf网站2345网址导航是病毒吗
  • wordpress批量定时更新温州seo排名优化