.
2019-02-02 吴亲库里 库里的深夜食堂
爬一个指定梯数的楼梯，有多少种方式。规则是每次你只能爬一步或者两步。
给定一个梯数是2,那么有两种方式,1.第一次走一步,第二次走一步 2.一次就走两步
首先我们考虑最简单的情况，当梯数为1时我们只有一种，也就是直接一步登顶，当梯数为2是，有两种，一是每次只爬一步，两次登顶，第二种直接一次爬两步。 我们可以把跳n层台阶看成是f(n)。当梯数n>2时，第一次跳就有两种不同的选择。如果选择跳一步的话，那么跳上n层台阶种类就等于剩下的f(n-1)总数。如果选择跳两步的话，剩下跳n层台阶种类等于f(n-2).这里得出的结论是当n>2时，f(n)=f(n-1)+f(n-2);上面的分析，其实我们使用的是动态规划，实际上是一个斐波那契数列,又称为黄金分割数列。这里我就不是用递归的方式实现了，递归实现的话容易造成节点的重复性，效率低下，比如说我要求$f(10),就要求$f(9)和$f(8),我要求$f(9),就要求$f(8)和$f(7),这样一层一层的依赖，他会随着n数的增大而剧增，加重了计算机的计算。
递归实现的话容易造成节点的重复性，效率低下，比如说我要求$f(10),就要求$f(9)和$f(8),我要求$f(9),就要求$f(8)和$f(7),这样一层一层的依赖，他会随着n数的增大而剧增，加重了计算机的计算。
function climbStairs($n) {
if($n<=2){
return $n;
}
$twoBack=1;$oneBack=2;
$currt=0;
for($i=3;$i<=$n;$i++){
$currt=$twoBack+$oneBack;
$twoBack=$oneBack;
$oneBack=$currt;
}
return $currt;
}
/**
* @param Integer $n
* @return Integer
*/
function climbStairs($n) {
if($n<=1){
return 1;
}
$res[0]=1;
$res[1]=1;
for($i=2;$i<=$n;$i++){
$res[$i]=$res[$i-1]+$res[$i-2];
}
return $res[$n];
}
