题目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
}
}
京公网安备 11010502036488号