Climbing Stairs

爬楼梯问题是一道典型的递归问题和动态规划问题的入门级题目。题目描述是：给定一个n个台阶楼梯，每次可以上一个或者两个台阶，请问最终可以有多少种方法爬到顶层。使用递归的思路解决是，到达第K个楼梯的方法数目是到达地k-1个楼梯的方法数与到达地k-2的楼梯的方法数的和。所以，如果函数原型是int cal(int n)，那么我们可以得到递归规则是cal(k)=cal(k-1)+cal(k-2）。边界条件是cal(1)=1,cal(2)=2。但是，这样计算会有很多的重复性计算，所以可以使用动态规划来解决。如果使用一位数组ways来存储到达第k个楼梯的方法数，那么ways[k+1] = ways[k]+ways[k-1];从0一直结算到n，可以避免很多的重复计算。该题目是leetcode上OJ的题目，也是CtCI的原题的变形。下面是给题目的Java实现。

public class Solution {

	/**
	 * You are climbing a stair case. It takes n steps to reach to the top.
	 * Each time you can either climb 1 or 2 steps. In how many distinct 
	 * ways can you climb to the top?
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(new Solution().climbStairs(10));

	}
	
	public int climbStairs(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
		
		if(n &lt; 0)
			return 0;
		
		int[] ways = new int [n+1];
		
		ways[0] = 1;
		ways[1] = 1;
		
		for(int i = 2; i &lt; n+1; i++){
			ways[i] = ways[i-1]+ways[i-2];
		}		
		return ways[n];        
       }

}