有n级楼梯，有2种爬法，1次1级，或1次2级，问，n级楼梯有多少种爬法？

一、递归求解

当n < 0时，无解，当n = 1 时，f ( n ) = 1， 当n = 2时，有两种方法，一次1级爬2次，或一次2级，
f （n） = 2。当 n > 2时，第一次跳一级还是两级，决定了后面剩下的台阶的跳法数目的不同：如果第一次只跳一级，则后面剩下的n-1级台阶的跳法数目为f(n-1)；如果第一次跳两级，则后面剩下的n-2级台阶的跳法数目为f(n-2)。所以，得出递归方程，f(n) = f(n-1) + f(n-2)。问题本质是斐波那契数列。

/**上台阶问题,递归求解**/
	public static int jumpStepFibonacci(int n,int m) {
		if(n<0) return -1;
		if(n<=2) return n;
		return jumpStepFibonacci(n-1, m)+jumpStepFibonacci(n-2, m);
	}

public static void main(String[] args) {
		
		int start = (int) System.nanoTime();
		
		System.out.println(jumpStepFibonacci(10, 2));
    	int end = (int)System.nanoTime();
		System.out.println("time:"+(end-start)+"ns");
	}

二、迭代法

迭代法和递归法相比，核心思想没有变，只是将递归方法变为迭代。

/**上台阶问题,迭代法**/
	public static int jumpStepIter(int n,int m) {
		if(n<0) return -1;
		if(n<=2) return n;
		int temp1 =1;
		int temp2 =2;
		int res = 0;
		for(int i =3;i<=n;i++) {
			res = temp1 + temp2;
			temp1 = temp2;
			temp2 = res;
		}
		return res;
	}

三、动态规划

/**上台阶问题，dp**/
	public static int climbStairs(int n) {
		if(n==0) return -1;
		if(n==1) return 1;
		int []dp = new int [n];
		dp[0] =1;
		dp[1] =2;
		for(int i=0;i<n-2;i++) {
			dp[i+2]=dp[i]+dp[i+1];
		}
		return dp[n-1];
	}

四、备忘录模式

摘自：https://blog.csdn.net/wu2304211/article/details/52717578

public static int dfs(int n, int[] array) {
        if (array[n] != 0) {
            return array[n];
        } else {
            array[n] = dfs(n - 1, array) + dfs(n - 2, array);
            return array[n];
        }
    }

    public static int fib03(int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1 || n == 2) {
            return n;
        } else {
            int[] array = new int[n + 1];
            array[1] = 1;
            array[2] = 2;
            return dfs(n, array);
        }
    }

总结

	public static void main(String[] args) {
		
		int n = 20,m=2;
		
		int start1 = (int) System.nanoTime();
		System.out.println(jumpStepFibonacci(n, m));
		int end1 = (int)System.nanoTime();
		System.out.println("递归:"+(end1-start1)+"ns");
		
		int start2 = (int) System.nanoTime();
		System.out.println(jumpStepIter(n, m));
		int end2 = (int)System.nanoTime();
		System.out.println("迭代:"+(end2-start2)+"ns");
		
		int start3 = (int) System.nanoTime();
		System.out.println(fib03(n));
		int end3 = (int)System.nanoTime();
		System.out.println("数组:"+(end3-start3)+"ns");
		
		
		int start5 = (int) System.nanoTime();
		System.out.println(climbStairs(n));
		int end5 = (int)System.nanoTime();
		System.out.println("dp:"+(end5-start5)+"ns");
	}

测试结果： n=20时，随机测了几次，明显看出，迭代法、备忘录模式、动态规划是一个数量级的，效率较递归高。