求问下面c++算法怎么理解?

假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?

int climbStairs(int n) {
int a = 1, b = 1;
while (n--)
{b=b+a;
a=b-a;//主要是这两句怎么理解?
}
return a;
}

谢谢

2个回答

这不就是fn = f(n - 1) + f(n -2) 的形式吗?
找规律就行啦,你多写几层的结果就会发现规律。
硬要说是算法的话,可以往dp上靠一靠

qq_30069409
wanwan_1996 回复Marconi25: 你自己写前5次所走的步数其实就是一个菲波那切数列。。。。。。一看就会了。
2 年多之前 回复
luopeng1217
Marconi25 为什么b=b+a; a=b-a;就是fn = f(n - 1) + f(n -2)的变换呢? 没怎么看懂
2 年多之前 回复

感觉过了一个星期了,这玩意,你应该自己想懂了吧。 b = b +a;那么b就是原来的a+b了 ,那么然后再来 a = b - a。那么a就是这个和减去现在的a,那么a就是原来的b了。那么经过这样的变换,b就是原来的那两玩意的和了,也就是 f(n-1) +f(n -2)。而a 变成了原来的那个b。也就是那个f(n-1)了。有兴趣,可以关注我,我打算最近打点算法,到我的博客中。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问