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

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

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

標簽:
JavaScript

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

课程内容:

今天学习的内容包括:
13-1 动态规划简介——解决子问题相互重叠的问题。
13-2 LeetCode:70. 爬楼梯——使用动态规划的f(n)=f(n-1)+f(n-2)计算有多少种方法。

课程收获:

动态规划

动态规划是什么
  • 动态规划是算法设计中的一种方法。
  • 它将一个问题分解为相互重叠的子问题,通过反复求解子问题,来解决原来的问题。
应用场景:斐波那契数列
  • 定义子问题:F(n) = F(n-1) + F(n-2)。
  • 反复执行:从2循环到n,执行上述公式。
动态规划 vs 分而治之
  • 子问题是否相互独立。

70. 爬楼梯

解题思路
  • 爬到第n阶可以在第n-1阶爬1个台阶,或者在第n-2阶爬2个台阶。
  • F(n) = F(n-1) + F(n-2)。
  • 使用动态规划。
解题步骤
  • 定义子问题:F(n) = F(n-1) + F(n-2)。
  • 反复执行:从2循环到n,执行上述公式。
for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
性能分析
  • 时间复杂度:O(n)。
  • 空间复杂度:O(n) or O(1)。

今天 通过 动态规划 学习了 爬楼梯有多少种方法的算法题,因为前端是重时间轻空间的,所以空间复杂度O(n)是可以接受的。一共学习了两种方法,对自己的思维有着一定的触发,对自己说一句,加油😀~

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

​​​​https://img1.sycdn.imooc.com//6326912f0001b5b625101348.jpg

https://img1.sycdn.imooc.com//6326950b00013da325211349.jpg

點擊查看更多內容
TA 點贊

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

評論

作者其他優質文章

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

100積分直接送

付費專欄免費學

大額優惠券免費領

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

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

幫助反饋 APP下載

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

公眾號

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

舉報

0/150
提交
取消