有2种算法, 递归和循环迭代, 依次介绍并比较
1.递归
1步台阶, 一种走法, 即f(1)=1;
2步台阶, 2种走法, 一步加一步或是直接跨两步, 即f(2)=2
3步台阶, 最后一次要么跨1步,要么跨2步, 一共的走法为最后一次跨1步的走法f(3-1)加上最后一次跨2步的走法f(3-2), 即f(3)=f(2)+f(1)
…
n步台阶, 最后一次跨1步的走法f(n-1)加上最后一次跨2步的走法f(n-2), 即f(n)=f(n-1)+f(n-2)
public class StepCount {private static int f(int n) {if (n == 1 || n == 2) {return n;} else {return f(n - 1) + f(n - 2);}}public static void main(String[] args) {long startTime = System.currentTimeMillis(); //记录初始时间System.out.println(f(40));long endTime = System.currentTimeMillis();//记录终末时间System.out.println("所用时间: " + (endTime - startTime) + " 毫秒");}}
走40步台阶耗时256毫秒
2.循环迭代
private static int f(int n) {if (n == 1 || n == 2) {return n;}//初始化为走到第二级台阶的走法int one = 2;//初始化为走到第一级台阶的走法int two = 1;int sum = 0;for (int i = 3; i <= n; i++) {//最后跨两步+最后跨一步的走法sum = two + one;two = one;//之前到目标阶跨一步的走法变成到下一目标阶跨两步的走法one = sum;//之前到目标阶的走法变成到下一目标阶跨一步的走法}return sum;}
同样走40步台阶, 耗时0毫秒
递归与循环迭代的比较
递归简洁、易于理解, 但是浪费空间、效率低下(从图中看出相对耗时更久)
迭代正好反之, 不够简洁, 可读性较差, 但是效率更高, 不易造成堆栈溢出
