题目1:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法?
对于这道题,我第一眼看到的想法是用递归的做法的,用递归的方法做题,我觉得最重要的就是找出 这个函数与下一个函数之间的关系 以及 一个函数体结束的临界条件(即递归的结束)。
例如就本题而言,
1.第一步先找这个函数与下一个函数之间的关系:
假如有n个台阶,跳上一个n级的台阶的跳法总数为f(n).
我们在跳的过程中,每一次有两种跳法,即跳一个或两个台阶。
第一种跳法:第一次跳了一个台阶,那么还剩下n-1个台阶还没跳,剩下的n-1个台阶的跳法有f(n-1)种。
或者用
第二种跳法:第一次跳了两个台阶,那么还剩下n-2个台阶还没跳,剩下的n-2个台阶的跳法有f(n-2)种。
由此不难得出递归公式:f(n) = f(n-1) + f(n-2);
2.第二步,找出递归的结束条件
当n <= 0时,跳法为0,即此时f(n) = 0
当只剩下一个台阶n = 1时,那么只有一种跳法,即f(1) = 1;
当n = 2时,此时跳法为2种,即f(2) = 2;
函数与函数之间的关系以及递归的临界条件都找出来了,那么接下来就可以开始写代码了。如下所示:
package com.bupt.practice;
/** * Created by zyx on 2019/3/28. **/
public class Frog_jumping_stairs_1 {
public static int f(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else if (n <= 0) {
return 0;
} else {
return f(n - 1) + f(n - 2);
}
}
public static void main(String[] args) {
long startTime = System.currentTimeMillis(); //获取开始时间
int x = f(40);
System.out.println("总共有" + x + "种跳法");//总共有165580141种跳法
long endTime = System.currentTimeMillis(); //获取结束时间
System.out.println("程序运行时间: " + (endTime - startTime) + "ms");//480ms
}
}
不过观察一下你就会发现,其实在递归的过程中,有很多相同的)f(n)重复算。
如下图:
算一下你就知道,时间复杂度是指数级别的。如果是比赛这样做的话,绝对超时不通过。
因此对于那些重复算过的,其实我们可以不用在重复递归来算它的,也就是所我们可以把f(n)算的结果一边给保存起来,这种就是动态规划的思想。
也就是说,我们可以把每次计算的结果保存中一个map容器里,把n作为key,f(n)作为value.然后每次要递归的时候,先查看一下这个f(n)我们是否已经算过了,如果已经算过了,我们直接从map容器里取出来返回去就可以了。如下:
package com.bupt.practice;
/** * Created by zyx on 2019/3/28. **/
import java.util.*;
public class Frog_jumping_stairs_2 {
//采用动态规划的方法
static Map<Integer, Integer> map = new HashMap<>();
public static int f1(int n) {
if (n <= 0) {
return 0;
} else if (n <= 2) {
return n;
} else {
if (map.containsKey(n)) {//查看是否存在
return map.get(n);
} else {//如果不存在则递归运算
int m = f1(n - 1) + f1(n - 2);
map.put(n, m);//保存起来
return m;
}
}
}
public static void main(String[] args) {
long startTime = System.currentTimeMillis(); //获取开始时间
int x = f1(40);
System.out.println("总共有" + x + "种跳法");//总共有165580141种跳法
long endTime = System.currentTimeMillis(); //获取结束时间
System.out.println("程序运行时间: " + (endTime - startTime) + "ms");//19ms
}
}
这种方***快很多很多。
实际上,对于f(n) = f(n-1) + f(n - 2)这种有递推关系的题,其实和斐波那契数列很相似,还可以这样做:
package com.bupt.practice;
/** * Created by zyx on 2019/3/28. **/
public class Frog_jumping_stairs_3 {
public static int f3(int n) {
if (n <= 0) {
return 0;
} else if (n <= 2) {
return n;
}
int f0 = 0;
int f1 = 1;
int f2 = 2;
int sum = 0;
for (int i = 3; i <= n; i++) {
sum = f1 + f2;
f1 = f2;
f2 = sum;
}
return sum;
}
public static void main(String[] args) {
long startTime = System.currentTimeMillis(); //获取开始时间
int x = f3(40);
System.out.println("总共有" + x + "种跳法");//总共有165580141种跳法
long endTime = System.currentTimeMillis(); //获取结束时间
System.out.println("程序运行时间: " + (endTime - startTime) + "ms");//17ms
}
}
问题2: 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。 求该青蛙跳上一个n级的台阶总共有多少种跳法?
分析,其实这道题和上面那道题一样的,只是本来每次跳有两种选择,现在有n中选择,即f(n) = f(n-1) + f(n - 2) + f(n-3)+…+f(1);
因此做法如下:
package com.bupt.practice;
/** * Created by zyx on 2019/3/28. **/
import java.util.*;
public class Frog_jumping_stairs_4 {
static Map<Integer, Integer> map = new HashMap<>();
public static int f4(int n) {
if (n <= 0) {
return 0;
} else if (n <= 2) {
return n;
} else {
if (map.containsKey(n)) {
return map.get(n);
} else {
int m = 0;
for (int i = 1; i < n; i++) {//相当于f(n) = f(n-1)+f(n-2)+…+f(1);
m += f4(n - i);
}
map.put(n, m);
return m;
}
}
}
public static void main(String[] args) {
long startTime = System.currentTimeMillis(); //获取开始时间
int x = f4(30);
System.out.println("总共有" + x + "种跳法");//总共有165580141种跳法
long endTime = System.currentTimeMillis(); //获取结束时间
System.out.println("程序运行时间: " + (endTime - startTime) + "ms");//16ms
}
}