# Leetcode:Climbing Stairs 斐波那契数

You are climbing a stair case. It takes n steps to reach
to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can
you climb to the top?

1. 递归，  f(n) = f(n-1) + f(n-2) 很容易想到递归，但是递归过程中存在大量的重复计算，会超时

2. 迭代

```class Solution {
public:
int climbStairs(int n) {
assert(n >= 0);
int prevTwo = 0;
int prevOne = 1;
int cur = 1;
for (int i = 1; i <= n; ++i) {
prevOne = cur;
cur = prevOne + prevTwo;
prevTwo = prevOne;
}
return cur;
}
};```

3. 直接计算：

```class Solution {
public:
int climbStairs(int n) {
assert(n >= 0);
double s = sqrt(5);
return floor((pow((1+s)/2, n+1) + pow((1-s)/2, n+1)) / s + 0.5);
}
};```

## [LeetCode] Climbing Stairs 斐波那契数列

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Show Tags 这题其实就是斐波那契数列来的. #include <iostream> using namespace std; class Solution {

## Project Euler 104:Pandigital Fibonacci ends 两端为全数字的斐波那契数

Pandigital Fibonacci ends The Fibonacci sequence is defined by the recurrence relation: F[n] = F[n-1] + F[n-2], where F[1] = 1 and F[2] = 1. It turns out that F541, which contains 113 digits, is the first Fibonacci number for which the last nine digi

## 分治法--二分查找、乘方、斐波那契数

1.二分查找 常见错误: 死循环:循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则,也就是说,如果循环体初始化时,是以左闭右开区间为边界的,那么循环体内部的迭代也应该如此.如果两者不一致,会造成程序的错误. 溢出:middle = left + (right - left) / 2 终止条件:一般来说,如果左闭右闭,则left<=right: 如果一开一闭,则left<right: 关键看left能不能等于right,而且要考虑实际情况,有时不能这样简单终结,会出现死循环