动态规划爬楼梯(为什么到i级的方法=i-1级的方法+到i-2级的方法)

简介: 想一想你现在就站在第i-1级台阶上,到达这第i-1级的台阶有100种方法,每一种方法都走到这里(第i-1级台阶),这100种方法中每一种方法都差一步就到第i级台阶了。

动态规划爬楼梯(为什么到i级的方法=到i-1级的方法+到i-2级的方法)

先附个原题

2345_image_file_copy_52.jpg

      初学动态规划,“爬楼梯”是必不可少的,但是相信有好多人都不理解问什么可以直接把变为斐波那契数列进而用到i-1级的方法+到i-2级的方法来求得到第i级台阶的方法。

      这是为什么呢?

     Because 最后一下确定了

如何理解呢?

(1)首先最后一步只有两种可能,①要么迈1级台阶②要么迈2级台阶

(2)那么到某级的方法就=所有最后迈1级台阶的方法+所有最后迈2级的方法。

(3)所有最后迈1级台阶的方法在dp[i-1],所有最后迈2级台阶的方法在dp[i-2]。(以到i级为例)


目录
打赏
0
0
0
0
4
分享
相关文章
2017级《算法设计与分析》--实验1--分治算法-骨牌铺方格
2017级《算法设计与分析》--实验1--分治算法-骨牌铺方格
2017级《算法设计与分析》--实验1--分治算法
2017级《算法设计与分析》--实验1--分治算法
软件体系结构 - 调度算法(2) 最低松弛度优先
【4月更文挑战第19天】软件体系结构 - 调度算法(2) 最低松弛度优先
263 0
【算法每日一练及解题思路】有n级台阶,一次只能上1级或2级,共有多少种走法?
本文深入解析了“爬楼梯问题”,探讨了递归与迭代两种解法,并提供了Java代码实现。通过分析问题本质,帮助读者理解动态规划技巧,提高解决实际编程问题的能力。关键词:Java, 算法, 动态规划, 爬楼梯问题, 递归, 迭代。
154 0
【见微知著】OpenCV中C++11 lambda方式急速像素遍历
【见微知著】OpenCV中C++11 lambda方式急速像素遍历
76 0
【错题集-编程题】mari和shiny(动态规划-多源状态线性 dp)
【错题集-编程题】mari和shiny(动态规划-多源状态线性 dp)
【浅谈算法】二分查找(保姆级)
【浅谈算法】二分查找(保姆级)
46 0
条件独立5条重要性质及其证明
本文给出了条件独立5条重要性质及其证明
255 0
条件独立5条重要性质及其证明
运筹规划时复杂条件转换(最大M方式)
运筹规划时复杂条件转换(最大M方式)
86 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等