You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
此问题反应了斐波那契数列的一个应用。
状态转移方程为f(x) = f(x-1)+f(x-2)
用递归解决此题,发现时间超限。因为递归会不断进栈出栈。
int climbStairs(int n)
{
int p = 0, q = 0, r = 1;
for (int i = 1; i <= n; i++)
{
p = q;
q = r;
r = p + q;
}
return r;
}
迭代方法,也是递归和动态规划的一种,只用了3个变量的滚动数组。性能提升。
原文:https://www.cnblogs.com/qianxinn/p/14622681.html