【Leetcode】70.爬楼梯

70 爬楼梯

题目：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

思路：

爬楼梯问题的本质是斐波那契数列，设对于n层台阶，爬到楼顶的方法数为climbStairs(n)。分为两种情况，第一步跳1阶，第2步跳2阶，方法数分别为climbStairs(n-1),climbStairs(n-2)。则climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)。
但用递归的方法实现时，会产生很多的重复计算。因此可以采用迭代的方法。即采用自下而上的方法取代自上而下的方法。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    //设对于n层台阶，爬到楼顶的方法数为climbStairs(n)
    //分为两种情况，第一步跳1阶，第2步跳2阶，方法数分别为climbStairs(n-1),climbStairs(n-2)
    //则climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)
    public int climbStairs(int n) {
        if(n == 0 || n == 1)
            return 1;
        if(n == 2)
            return 2;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <=n ; i++)
            dp[i] = dp[i-1] + dp[i - 2];
        return dp[n]; 
    }
}