70. 爬楼梯

题意：

解题思路：

思路：
状态定义：f[i] 表示上 i 级台阶的方案数
转移方程：枚举最后一步是上1级台阶，还是上2级台阶 =》 f(n) = f(n-1) + f(n-2)
复杂度分析：递推状态数 O(n)，转移时间复杂度是 O(1)，所以总时间复杂度是 O(n)

PHP代码实现：

class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function climbStairs1($n) {
        if ($n < 2) {
            return 1;
        }
        return $this->climbStairs($n - 1) + $this->climbStairs($n -2);  
    }
    function climbStairs($n) {
        return $this->climstairDp1($n);
        //return $this->climbstairFab($n);
        //return $this->climbStairDp($n);
        //return $this->climbStairsDfs(0, $n);    
        //$memo = array_fill(0, $n + 1, 0);  
        //return $this->climbStairsDfsMemo(0, $n, $memo);
    }
    /*
        楼梯数：3:
        f[i-1]: 2 -> 1 //在第 (i-1)(i−1) 阶后向上爬一阶 2 + 1
        f[i-2]: 1 => 2 //在第 (i−2) 阶后向上爬 2 阶, (1+1+1) (1+2)
    */
    function climbStairDp($n) {
        if ($n == 1) return 1;
        $dp = array_fill(0, $n + 1, 0);
        $dp[1] = 1;  $dp[2] = 2;
        for ($i = 3; $i <= $n; $i++) {
            $dp[$i] = $dp[$i - 1] + $dp[$i - 2];
        }
        return $dp[$n];
    }
    //因为后面的只会依赖前面2个值 O(n)
    function climstairDp1($n) {
        if ($n == 1) return 1;
        if ($n == 2) return 2;
        $first = 1;
        $second = 2;
        for ($i = 3; $i <= $n; $i++) {
            $third = $first + $second;
            $first = $second;
            $second = $third;
        }
        return $second;
    }
    //斐波那契数(Time Limit Exceeded)
    function climbstairFab($n) {
        if ($n < 2) return 1;
        return $this->climbstairFab($n - 1) + $this->climbstairFab($n - 2);
    }
    //O(2^n) TLE
    function climbStairsDfs($i, $n) {
        if ($i > $n) return 0;
        if ($i == $n) return 1;
        return $this->climbStairsDfs($i + 1, $n) + $this->climbStairsDfs($i + 2, $n);
    }
    //O(n)树形递归的大小可以达到 n。 //TLE
    function climbStairsDfsMemo($i, $n, $memo) {
        if ($i > $n) return 0;
        if ($i == $n) return 1;
        if ($memo[$i] > 0) return $memo[$i];
        $memo[$i] = $this->climbStairsDfsMemo($i + 1, $n, $memo) + $this->climbStairsDfsMemo($i + 2, $n, $memo);
        return $memo[$i];
    }
}

GO代码实现：

func climbStairs(n int) int {
    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2
    }
    return climbStairs(n-2) + climbStairs(n-1)
}
func climbStairs1(n int) int {
    var result = []int{0, 1, 2}
    for i := 3; i <= n; i++ {
        result = append(result, result[i-1] + result[i-2])
    }
    return result[n]
}
func climbStairs2(n int) int {
    var first, second = 1, 2
    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2
    }
    for i := 3; i <= n; i++ {
        first, second = second, first + second
    }
    return second
}