《剑指offer》面试题10(题目二)扩展问题:
题目:在青蛙跳台阶的问题中,如果把条件改成:一只青蛙一次可以跳上1级台阶,也可以跳上2级...也可以跳上n级,此时该青蛙跳上一个n级的台阶总共有多少种跳法?
思路:设该青蛙跳上一个n级的台阶总共有f(n)种跳法,第一次跳1级,则剩下的台阶有f(n-1)种跳法;第一次跳2级,则剩下的台阶有f(n-2)种跳法;......第一次跳n-1级,则剩下的台阶有f(1)种跳法。故f(n)= f(n-1)+ f(n-2)+ f(n-3)+ ... + f(1)。而f(n-1)= f(n-2)+ f(n-3)+ f(n-4)+...+ f(1)。两式相减得f(n)= 2 * f(n-1)。
代码如下:
public int jumpFloor(int n) {
if (n <= 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return 2 * jumpFloor(n - 1);
}
}