亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定

【九月打卡】第15天 算法設計思想之“動態規劃”

標簽:
JavaScript

课程名称:JavaScript版数据结构与算法
课程章节:第13章 算法设计思想之“动态规划”
主讲老师:lewis

课程内容:

今天学习的内容包括:
13-3 LeetCode:198. 打家劫舍——使用动态规划,把各种可能性分别计算后合并得到解。
13-4 动态规划-章节总结——动态规划的定义以及解题方法。
13-5 【勤于思考,夯实学习成果】阶段思考题——完成对应作业。

课程收获:

198. 打家劫舍

解题思路
  • f(k)=从前k个房屋中能偷窃到的最大数额。
  • Ak =第k个房屋的钱数。
  • f(k)= max(f(k -2)+ Ak, f(k - 1))。
  • 考虑使用动态规划。
解题步骤
  • 定义子问题: f(k)= max(f(k -2)+ Ak, f(k - 1))。
  • 反复执行:从2循环到n,执行上述公式。
    dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
性能分析
  • 时间复杂度:O(n)。
  • 空间复杂度:O(n) || O(1)。

章节总结

动态规划是什么
  • 动态规划是算法设计中的一种方法。
  • 它将一个问题分解为相互重叠的子问题,通过反复求解子问题,来解决原来的问题。
动态规划的步骤
  • 定义子问题。
  • 反复执行。
  • 合并处理结果。

今天 通过 动态规划 学习了 打家劫舍算法题,今天有种感觉就是算法好像对数学的要求还是有的,明显感觉自己的数学能力不够,理解算法有点吃力,对自己说一句,加油😀~

坚持打卡,坚持学习!明天见💪~

​​​​https://img1.sycdn.imooc.com//6327cdbc00019cb225201433.jpg

https://img1.sycdn.imooc.com//6327e18d0001851225261456.jpg

點擊查看更多內容
TA 點贊

若覺得本文不錯,就分享一下吧!

評論

作者其他優質文章

正在加載中
  • 推薦
  • 評論
  • 收藏
  • 共同學習,寫下你的評論
感謝您的支持,我會繼續努力的~
掃碼打賞,你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃,即可進行掃碼打賞哦
今天注冊有機會得

100積分直接送

付費專欄免費學

大額優惠券免費領

立即參與 放棄機會
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號

舉報

0/150
提交
取消