【LeetCode】70. 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?

Note: Given n will be a positive integer.

Example 1:

Input: 2

Output: 2

Explanation: There are two ways to climb to the top.

1. 1 step + 1 step

2. 2 steps

Example 2:

Input: 3

Output: 3

Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step

2. 1 step + 2 steps 3. 2 steps + 1 step

 解题思路：

（1）递归解法（此方法在LeetCode中时间超时）

爬上n阶台阶有两种情况：从第n-1阶台阶往上爬，或者是从n-2阶台阶网上爬。那么爬上n-1阶台阶也有两种情况：从n-2阶台阶往上爬1个台阶，或者是从n-3阶台阶往上再爬2阶。以此类推。

我们可以写出递推公式，f(n)是爬上n阶台阶的方法数。

在写代码的时候，我们可以假设f(0)=1，也就是没有台阶的时候有1种上法。

public class ClimbingStairs_70 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(climbStairs(4));
	}
	
    public static int climbStairs(int n) {
    	return calcWays(n);
    }
    
    public static int calcWays(int n) {
    	if(n == 0 || n==1) {
    		return 1;
    	}
    	return calcWays(n-1) + calcWays(n-2);
    }

}

（2）记忆化搜素方式：一种优化递归解法（此方法可以在LeetCode中AC）

由于递归解法重复的计算，我们可以把之前计算过的数值保存到数组里面，每次搜素之前n-1的值和n-2的值。

import java.util.Arrays;

public class ClimbingStairs_70 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(climbStairs(4));
	}
	
	public static int[] memo;
    public static int climbStairs(int n) {
    	memo = new int[n+1];
    	Arrays.fill(memo, -1);
    	return calcWays(n);
    }
    
    public static int calcWays(int n) {
    	if(n == 0 || n==1) {
    		return 1;
    	}
    	if(memo[n] == -1) {
    		memo[n] = calcWays(n-1) + calcWays(n-2);
    	}
    	return memo[n];
    }

}

（3）动态规划解法（此方法可以在LeetCode中AC）

import java.util.Arrays;

public class ClimbingStairs_70 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(climbStairs(4));
	}
	
    public static int climbStairs(int n) {
        int[] memo = new int[n+1];
        Arrays.fill(memo, -1);
        memo[0] = 1;
        memo[1] = 1;
        for(int i=2; i<=n; i++) {
        	if(memo[i] == -1) {
        		memo[i] = memo[i-1] + memo[i-2];
        	}
        }
    	return memo[n];
    }

}