[Leetcode 系列] 70. Climbing Stairs 爬梯子的php解法

本质是一个排列组合问题。给出长度n，最多有floor(n/2)个2级，最少0个2级。然后从0开始到floor(n/2)遍历，求2级和1级的排列组合。

<?php
class Solution {

    /**
     * @param Integer $n
     * @return Integer
     */
    function climbStairs($n) {
        $twoNum=intval($n/2);
        $combineNum=0;
        for($t=0;$t<=$twoNum;$t++){
            $oneNum=$n-$t*2; // 剩余都是1级的
            $spot=$oneNum+$t;
            $combineNum+=($this->fact($spot)/($this->fact($oneNum)*$this->fact($t))); // 排列组合公式
        }
        return $combineNum;
    }

    /**
     * 求阶乘
     * @param $n
     * @return float|int
     */
    function fact($n){
        if($n===0){
            return 1;
        }
        return array_product(range(1,$n));
    }
}

复习一下排列组合