关于青蛙跳的问题解答
import java.util.Date;public class Frag {public static int STEP;public static int TOT = 0;public static String tmpprint;public static void goNextJump(int currentStep, int length, String print) {if (currentStep == STEP) {if (!print.equals(tmpprint)) {TOT = TOT + 1; System.out.println(print + "(TOT=" + TOT + ")");tmpprint = print;}return;} else {if (currentStep + length <= STEP) {print = print + "-->" + length;currentStep = currentStep + length;goNextJump(currentStep, 1, print);goNextJump(currentStep, 2, print);}return;}}public static int getTot(int step) {STEP = step;if (step == 0) {return 0;}if (step == 1) {return 1;}String print = "0";goNextJump(0, 1, print);goNextJump(0, 2, print);return TOT;}public static void main(String[] args) {Date start = new Date();System.out.println(getTot(20));Date end = new Date();System.out.println(end.getTime() - start.getTime());}}
? 我的同事Vivi给出了强大的答案
/** * @description 一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法 * @author vivi_zhao * @date Dec 30, 2011 */public class Frog {public long[] a;public boolean[] isExist;void init(int n) {a = new long[n + 1];isExist = new boolean[n + 1];}long hoopWithMemory(int n) {if (n < 0)return 0;if (n == 0)return 1;if(!isExist[n]) {isExist[n] = true;return a[n] = hoopWithMemory(n - 2) + hoopWithMemory(n - 1);}return a[n];}long hoopWithoutMemory(long n) {if(n < 0)return 0;if(n == 0)return 1;return hoopWithoutMemory(n - 1) + hoopWithoutMemory(n - 2);}public static void main(String[] args) {Frog frog = new Frog();int count = 50;long start = System.currentTimeMillis();//hoop with memoryfrog.init(count);start = System.currentTimeMillis();System.out.println(frog.hoopWithMemory(count));long end = System.currentTimeMillis();System.out.println(frog.hoopWithoutMemory(count));long end2 = System.currentTimeMillis();System.out.println("(hoop with memory = " + (end - start) + ") << (hoop without memory = " + (end2 - end) + ")");}}??