在算法书里，我们总能看得到一道经典的题目。

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

我们可以利用分治法来解决这一题。首先需要找到上台阶子问题的分割方法，再递归地求解子问题，最后把所有子问题的结果合并。

很容易看出，只有1级台阶的时候，只有1种跳法。2级台阶有2种跳法，3级台阶有3种跳法。如果有4级台阶，有5种跳法。

怎么求呢？我们可以把求解4级台阶，分解成求解两个2级台阶的子问题。这样一来，我们可以算出2×2种不同的跳法【1-2-3-4，12-3-4，1-2-34，12-34】。需要注意的是，分解成两个子问题之后，还会有跨越这两个子问题的情况。在本题中，跨越子问题的情况只可能是从前一个子问题，到下一个子问题，走过了两级台阶。在4级台阶中，这种情况是【1-23-4】

所以我们在合并所有子问题的时候，将上述两种情况合并起来就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        return self.helper(number)
        
    def helper(self, number):
        if (number <= 3):
            return number
       	else:
            if (number % 2 == 0):
                # 台阶个数为偶数，恰好能等分成两个子问题
                # 子问题内的跳法个数 + 跨越子问题的跳法个数
            	return self.helper(number / 2) * self.helper(number / 2) + self.helper(number / 2 - 1) * self.helper(number / 2 -1)
            else:
                # 台阶个数为奇数，分割子问题的时候尽量均分
                # 子问题内的跳法个数 + 跨越子问题的跳法个数
                return self.helper(number / 2) * self.helper(number - number / 2) + self.helper(number / 2 - 1) * self.helper(number - number / 2 -1)