题目: 一只青蛙一次可以跳上 1 级台阶, 也可以跳上 2 级...... 它也可以跳上 n 级. 求该青蛙跳上一个 n 级的台阶总共有多少种跳法.
关于本题, 前提是 n 个台阶会有一次 n 阶的跳法. 分析如下:
- f(1) = 1
- f(2) = f(2-1) + f(2-2) //f(2-2) 表示 2 阶一次跳 2 阶的次数.
- f(3) = f(3-1) + f(3-2) + f(3-3)
- ...
- f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)
说明:
1) 这里的 f(n) 代表的是 n 个台阶有一次 1,2,...n 阶的 跳法数.
2)n = 1 时, 只有 1 种跳法, f(1) = 1
3) n = 2 时, 会有两个跳得方式, 一次 1 阶或者 2 阶, 这回归到了问题 (1) ,f(2) = f(2-1) + f(2-2)
4) n = 3 时, 会有三种跳得方式, 1 阶, 2 阶, 3 阶,
那么就是第一次跳出 1 阶后面剩下: f(3-1); 第一次跳出 2 阶, 剩下 f(3-2); 第一次 3 阶, 那么剩下 f(3-3)
因此结论是 f(3) = f(3-1)+f(3-2)+f(3-3)
5) n = n 时, 会有 n 中跳的方式, 1 阶, 2 阶...n 阶, 得出结论:
f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)
6) 由以上已经是一种结论, 但是为了简单, 我们可以继续简化:
- f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
- f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
可以得出:
f(n) = 2*f(n-1)
7) 得出最终结论, 在 n 阶台阶, 一次有 1,2,...n 阶的跳的方式时, 总得跳法为:
- | 1 ,(n=0 )
- f(n) = | 1 ,(n=1 )
- | 2*f(n-1),(n>=2)
- public class Solution {
- public int JumpFloorII(int target) {
- if(target <= 2){
- return target;
- }
- return 2*JumpFloorII(target-1);
- }
- }
来源: http://www.bubuko.com/infodetail-3145208.html