首页 > 代码库 > 一只青蛙从第一级台阶跳到第n级，每次可以跳任意级，共有多少种跳法，并写出递推式
一只青蛙从第一级台阶跳到第n级，每次可以跳任意级，共有多少种跳法，并写出递推式
是斐波那契数列问题
假设f(n)是n个台阶跳的次数：(假设已经调到第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-2) + f(n-1) == f(n) = 2*f(n-1)
所以，可以得出递推式:
1 public static int jumpFloor(int n) { 2 if (n <= 0) 3 return 0; 4 if (n == 1) 5 return 1; 6 return 2 * jumpFloor(n - 1); 7 }
跳台阶，一次只能夸1个、2个和3个台阶，解法类似：
1 public static int cnt(int n){ 2 int[]dic = {0,1,2,4}; 3 if ( n <= 3) 4 return dic[n]; 5 return cnt(n-1) + cnt(n-2) + cnt(n-3); 6 }
一只青蛙从第一级台阶跳到第n级，每次可以跳任意级，共有多少种跳法，并写出递推式
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。