算法面试真题详解:爬楼梯-阿里云开发者社区

开发者社区> 算法编程> 正文
登录阅读全文

算法面试真题详解:爬楼梯

简介: 算法面试真题详解:爬楼梯

描述
假设你正在爬楼梯,需要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];
    }
}

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接