变态青蛙跳台阶

青蛙跳台阶，跳的阶数不限，跳到第n阶时有几种跳法

package com.art.arithmetic.count;

public class FrogJumpOrderNoLimit {

	public static void main(String[] args) {
		FrogJumpOrderNoLimit frogJumpOrder = new FrogJumpOrderNoLimit();
		System.out.println(frogJumpOrder.getMethodNumNoLimit(4));
		System.out.println(frogJumpOrder.getMethodNumNoLimit(5));
		System.out.println(frogJumpOrder.getMethodNumNoLimit(6));
		System.out.println(frogJumpOrder.getMethodNumNoLimit(7));
		System.out.println(frogJumpOrder.getMethodNumNoLimit(8));
	}
	
	/**
	 * 青蛙跳台阶，一次可跳一阶或两阶，跳到第n阶时有几种跳法
	 * 能跳到第n阶的方式有从n-1阶跳或从n-2阶跳，那么就需要获取跳到n-1和n-2时各有多少种方法，依次类推
	 * @return
	 */
	public long getMethodNum(long n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		if (n == 2) {
			return 2;
		}
		return getMethodNum(n-1) + getMethodNum(n-2);
	}

	/**
	 * 和上面方法类似，这里不做限制后，相当于前面每一阶都能跳到第n阶，所以要将前面的所有跳到的阶数累加，然后它也可以一次直接登顶，所以累加后要加1
	 * 1   1
	 * 2   1 + 1 = 2  
	 * 3   1 + 2 + 1 = 4
	 * 4   1 + 2 + 4 + 1 = 8
	 * 5   1 + 2 + 4 + 8 + 1 = 16
	 * 由此推论出跳的方法为2^n
	 * @return
	 */
	public long getMethodNumNoLimit(long n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		long sum = 1;
		for (int i = 2; i <= n; i++) {
			sum *= 2;
		}
		return sum;
	}

}