题解 1861: 程序员爬楼梯

解题思路:

注意事项:

参考代码:

import java.util.Scanner;


public class 爬楼梯 {

	/**
	 * @param args
	 */
	static int book [];//备忘录
	public static void main(String[] args) {
		// TODO Auto-generated method stub
      // 一次爬1 或者 3
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		book=new int[n+1];//备忘录
		System.out.println(dg(n));
		
	}

	private static int dg(int n) {
		// TODO Auto-generated method stub
		if (n==1||n==2) {//当1阶或者2阶楼梯时  那么只有一种方法
			return 1;
		}
		if (n==3) {//当 3阶时  要么是1+1+1 要么是 3  所以两种方法
			return 2;
		}
		else if(book[n]==0){//初始值为0
			book[n]=dg(n-1)+dg(n-3);//倒推 当前可以阶梯是 由n-1阶 或者 n-3阶
			return book[n];
		}
		else {
			return book[n];
		}
	}

}