[LeetCode] Climbing Stairs

Well, a classic and interesting problem. The recursion is simply f(n) = f(n - 1) + f(n - 2), which means that we can either climb to n - 1 and then climb 1 step or climb to n - 2 and then climb 2 steps. So this problem is actually asking for the n-th Fibonacci number. However, if you code it in such a recursive way, it will meet TLE due to the large number of overlapping sub-problems.

There are mainly two ways to solve this problem. The first one uses the above formula in a bottom-up manner and takes O(n) time. This link shares the O(n) solution in all the supported languages of the LeetCode OJ. You may take a look at it and appreciate the appetite of each language :-)

Now I will focus on another solution, which takes O(logn) time. The idea is to use the matrix power. In fact, [f(n), f(n - 1); f(n - 1), f(n - 2)] = [1, 1; 1, 0]^(n - 1) for n >= 2. And similar to the problem Pow(x, n), the power of a matrix can be computed in O(logn) time.

Both C++ and Python codes are shown below. The flexible swapping statement in Python brings great convenience while the body of the for-loop in the function int fibPower(int n) is actually taken from the above link. Note that the computation of the power of the matrix [a, b; c, d] = [1, 1; 1, 0] is hard-coded.

C++

 1 class Solution { 
 2 public:
 3     int climbStairs(int n) {
 4         return fibPower(n);
 5     }
 6 private:
 7     int fibPower (int n){
 8         int a = 1, b = 1, c = 1, d = 0;
 9         for (int i = 0; i < n - 1; i++) {
10             b = (a += b) - b;
11             d = (c += d) - d;
12         }
13         return a;
14     }
15 };

Python

class Solution:
    # @param {integer} n
    # @return {integer}
    def climbStairs(self, n):
        a, b, c, d = 1, 1, 1, 0 
        for i in range(n - 1):
            a, b, c, d = a + b, a, c + d, c
        return a

[LeetCode] Climbing Stairs

原文：http://www.cnblogs.com/jcliBlogger/p/4647030.html