题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶
题解
思路1: 动态规划
设dp[i]为爬到i阶的不同方法数
dp[i]的转移方程为：
dp[i] = dp[i-1]+dp[i-2] (i>2)
边界条件:dp[1]=1,dp[2]=2
// OC
+ (int)climbStairs1:(int)n {
if (n <= 2) {
return n;
}
int dp[n+1];
dp[1] = 1;
dp[2] = 2;
for (int i=3; i<n+1; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
// Swift
static public func climbStairs1(_ n:Int) -> Int {
if n <= 2 {return n}
var dp = Array(repeating: 0, count: n+1)
dp[1] = 1
dp[2] = 2
for i in 3..<(n+1){
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
思路2:通项公式
设f(n)为爬到n阶的不同方法数
f(n) =f(n-1)+f(n-2) (n>2)
f(1) = 1 f(2)= 1 f(3) = 2
f(n)是齐次线性递推,根据递推公式f(n) = f(n-1)+f(n-2)，我们可以写出这样的特征方程
x*x=x+1,求得x1 = (1+ √5)/2，x2 = (1-√5)/2。设通解为f(n) = c1x1^n + c2x2^n,代入初始条件f(1) = 1,f(2) = 1,
得c1 = 1/(√5),c2 = -1/(√5),我们得到了这个递推数列的通项公式
f(n) = 1/√5*(((1+√5)/2)^n - ((1-√5)/2)^n)
// OC
+ (int)climbStairs2:(int)n {
double sqrt5 = sqrt(5);
double fibn = pow((1+sqrt5)/2, n+1) - pow((1-sqrt5)/2, n+1);
int res = (int)round(fibn/sqrt5);
return res;
}
// Swift
static public func climbStairs2(_ n:Int) -> Int {
let sqrt5:Double = sqrt(5)
let fibn:Double = pow((1+sqrt5)/2, Double(n+1)) - pow((1-sqrt5)/2, Double(n+1))
let res:Int = Int(round(fibn/sqrt5))
return res
}
参考：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn854d/
https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/
