2019-09-13 爬楼梯问题

假设你正在爬楼梯。需要 n 步你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 步 + 1 步
2.  2 步
示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 步 + 1 步 + 1 步
2.  1 步 + 2 步
3.  2 步 + 1 步

分析：
当每次爬一步时，步数最多，为n：

当每次爬两步时，步数最少，为：n/2（先下取整n-1/2）

然后，步数肯定介于两者之间，我们从n开始考虑，当有一次走的是两步时：
可能是下图中任意两次一步合为一次：

有多少种可能呢？ n-1 种。

当有两次走的是两步：
得分两步来处理：两边、中间
对于两边：没融合一个，减少两个可融合位置
对于中间，每融合一个，减少三个可融合位置

可以用排列组合来

通过代码：

var climbStairs = function(n) {
    
    var min = (n+1)/2, max = n, com = 0;
    var ways=1;
    for(var j=max;j>min;){
        ways += combaine(++com,--j);
    }
    return ways;
};
function combaine(m,n)   // n>m    === n in m
{
    var denominator = n,numerator=1,result = 0;
    if(n==1){
        result = m;
    }
    else{
        for(var i=0;i<m-1;i++)
        {
            denominator = denominator*(--n);
            numerator = numerator * (i+2);
            if(denominator%numerator == 0)
            {
                denominator = denominator/numerator;
                numerator = 1;
            }
        }
        result = denominator/numerator;
    }
    return result;
}