题目

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:

  1. Input: 2
  2. Output: 2
  3. Explanation: There are two ways to climb to the top.
  4. 1. 1 step + 1 step
  5. 2. 2 steps

Example 2:

  1. Input: 3
  2. Output: 3
  3. Explanation: There are three ways to climb to the top.
  4. 1. 1 step + 1 step + 1 step
  5. 2. 1 step + 2 steps
  6. 3. 2 steps + 1 step

题意

给定一个高度为n的楼梯，每次可以向上走1层或2层，统计可以登顶的方法的个数。

思路

动态规划：dp[i]代表能够走到第i层的方法的个数，而第i层只可能由第i-1层走1层到达，或由第i-2层走2层到达，所以有 0070. Climbing Stairs (E) - 图1。

递归：从当前层i走到最高层的方法数等于从i+1层走到最高层的方法数加上i+2层走到最高层的方法数。

代码实现

Java

动态规划

  1. class Solution {
  2.     public int climbStairs(int n) {
  3.         int[] dp = new int[n];
  4.         dp[0] = 1;
  5.         for (int i = 1; i < n; i++) {
  6.             dp[i] = dp[i - 1] + (i > 1 ? dp[i - 2] : 1);
  7.         }
  8.         return dp[n - 1];
  9.     }
  10. }

递归

  1. class Solution {
  2.     public int climbStairs(int n) {
  3.         int[] ways = new int[n + 1];    // 避免重复运算
  4.         return findWays(0, n, ways);
  5.     }
  7.     // 返回从第i层走到第n层的方法数
  8.     private int findWays(int i, int n, int[] ways) {
  9.         if (i == n) {
  10.             return 1;
  11.         }
  12.         if (i > n) {
  13.             return 0;
  14.         }
  16.         if (ways[i] > 0) {
  17.             return ways[i];
  18.         }
  20.         ways[i] = findWays(i + 1, n, ways) + findWays(i + 2, n, ways);
  21.         return ways[i];
  22.     }
  23. }

JavaScript

  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var climbStairs = function (n) {
  6.   let dp = [1, 2]
  7.   for (let i = 2; i < n; i++) {
  8.     dp[i] = dp[i - 2] + dp[i - 1]
  9.   }
  11.   return dp[n - 1]
  12. }