Climbing Stairs @LeetCode

package Level2;

import java.util.Arrays;

/**
 * Climbing Stairs
 * 
 *  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?if
 *
 */
public class S70 {

	public static void main(String[] args) {
		System.out.println(climbStairs(1));
	}
	
	public static int climbStairs(int n) {
		// dp数组，用来保存结果，可以适当开大一些
        int[] dp = new int[n+5];		
        Arrays.fill(dp, -1);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        return rec(n, dp);
    }
	
	// 递归+dp
	private static int rec(int n, int[] dp){
		if(dp[n] != -1){
			return dp[n];
		}else{
			dp[n] = rec(n-1, dp) + rec(n-2, dp);
			return dp[n];
		}
	}

}