Question:
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?
Analysis:
问题描述：有一个爬梯子的问题。到达顶部需要n步。每次你可以爬1步或者2步。那么到达顶层一共有多少种不同的方式？
思路：要到达第n层，只能由第n-1层爬1步到达，或者由第n-2层爬2步到达。这样第n层的路径数就等于n-1层的路径数加n-2层的路径数。这样就是一个典型的动态规划（Dynamic Programing）问题。
dp[n] = dp[n-1] + dp[n+1];
Answer:
public class Solution { public int climbStairs(int n) { if(n == 0 || n == 1 || n == 2) return n; int[] temp = new int[n+1]; temp[0] = 0; temp[1] = 1; temp[2] = 2; for(int i=3; i<n+1; i++) { temp[i] = temp[i-1] + temp[i-2]; } return temp[n]; } }
思路二：用递归法实现。但是递归效率一般不高，因此时间会超时。
public class Solution { public int climbStairs(int n) { if(n == 0 || n == 1 || n == 2) return n; return climbStairs(n - 1) + climbStairs(n - 2); } }
原文：http://www.cnblogs.com/little-YTMM/p/4846318.html