今天看到一个斐波纳切问题的变形，觉得很有意思，遂记录一下：
一个青蛙爬楼梯，他可以一次跳一节台阶，也可以跳两节，还可以后退一节，问：高度为n的台阶共有多少种方式到达。
首先分析一下，对任意一个位置i（i>2)，到达的方式与i+1, i-1, i-2 三个位置有关，即s(i) = s(i+1) + s(i-1) + s(i-2)，而不在位置i上停留到达位置i+1的方式只有一种：从i-1位置跳2节，即s(i+1)=s(i-1), 即s(i) = 2s(i-1) + s(i-2)，有了状态转移方程，我们即可进行求解。
def solve(n):
if n == 1:
return 2
elif n == 2:
return 3
return 2*solve(n-1) + solve(n-2)
接触DP最早的应该就是这道题了吧，翻了翻leetcode submission发现最早的是在一年前... 而且是最...
今天看到一个斐波纳切问题的变形，觉得很有意思，遂记录一下： 一个青蛙爬楼梯，他可以一次跳一节台阶，也可以跳两节，还...
常规动态规划问题 相关题目： 70.爬楼梯 70.爬楼梯 描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每...
一个Ｎ阶的楼梯，每次能１或着２阶，问走n阶的楼梯有多少种走法? 分析可知在走第ｎ阶的时候，是与第n-1阶和n-2阶...
问题来源 可爱的小明特别喜欢爬楼梯，他有的时候一次爬一个台阶，有的时候一次爬两个台阶，有的时候一次爬三个台阶。如果...
今天面试遇到了这个题,脑子轴了一下, 没有答上来, 事后想了想, 其实也是蛮简单的问题 牛顿爬楼梯.png 爬楼梯...
问题链接 70. 爬楼梯[https://leetcode-cn.com/problems/climbing-st...
爬楼梯可以瘦大腿妈?爬楼梯在生活中很常见，爬楼梯其实也是一种运动，很多女性想通过爬楼梯来瘦大腿，那么，爬楼梯可以瘦...
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢...
爬楼梯问题 1. 题目 爬楼梯每次可以爬1阶或两阶，问到n阶有多少种方法 2. 思路 状态：dp[i]表示到第i阶...
本文标题：爬楼梯问题
本文链接：https://www.haomeiwen.com/subject/grkwwqtx.html
网友评论