描述

假设你正在爬梯，需要 n 步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到顶部？

在线评测地址

样例 1

        输入:  n= 3         输出: 3                  样例解释：         1) 1, 1, 1         2) 1, 2         3) 2, 1         共 3 种 

样例 2

        输入:  n = 1         输出: 1                  解释:           只有一种方案 

算法思路

• 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?
• 考虑最后一步走 1 阶还是走 2 阶。 方案数 Dpn = 最后一步走 1 阶的方案数 + 最后一步走 2 阶的方案数。Dpn = Dpn-1 + Dpn-2.

public class Solution {     public int climbStairs(int n) {         if (n <= 1) {             return n;         }         int last = 1, lastlast = 1;         int now = 0;         for (int i = 2; i <= n; i++) {             now = last + lastlast;             lastlast = last;             last = now;         }         return now;     } }  // 记忆化搜索 // 九章硅谷求职算法集训营版本 public class Solution {     /**      * @param n: An integer      * @return: An integer      */     int[] result = null;      void f(int X) {          if (result[X] != -1) return;                                                           if (X == 0 || X == 1) {             result[X] = 1;             return;          }                    f(X - 1);          f(X - 2);          result[X] = result[X - 1] + result[X - 2];     }      public int climbStairs(int n) {         if (n == 0) {             return 0;         }                  result  = new int[n + 1];         for (int i = 0; i <= n; ++i) {             result[i] = -1;         }                  f(n);         return result[n];     } } 

更多题解参考

大佬有話說 (0)