专栏首页武培轩的专栏Leetcode#70. Climbing Stairs(爬楼梯)

Leetcode#70. Climbing Stairs(爬楼梯)

题目描述

假设你正在爬楼梯。需要 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 阶

思路

思路一:

递归

思路二:

用迭代的方法,用两个变量记录f(n-1) f(n-2)

代码实现

package DynamicProgramming;

/**
 * 70. Climbing Stairs(爬楼梯)
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
 */
public class Solution70 {
    public static void main(String[] args) {
        Solution70 solution70 = new Solution70();
        System.out.println(solution70.climbStairs(3));
    }

    /**
     * 直接用递归
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        } else {
            return climbStairs(n - 1) + climbStairs(n - 2);
        }
    }

    /**
     * 用迭代的方法,用两个变量记录f(n-1) f(n-2)
     *
     * @param n
     * @return
     */
    public int climbStairs_2(int n) {
        int one = 1, two = 2, fN = 0;
        if (n <= 0) {
            return 0;
        } else if (n <= 2) {
            return n;
        } else {
            for (int i = 3; i <= n; i++) {
                fN = one + two;
                one = two;
                two = fN;
            }
            return fN;
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode#191. Number of 1 Bits(位1的个数)

    编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。

    武培轩
  • 剑指Offer-变态跳台阶

    package Recursion; /** * 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳...

    武培轩
  • Leetcode#461. Hamming Distance(汉明距离)

    武培轩
  • C#版 - Leetcode 633. 平方数之和 - 题解

    在线提交: https://leetcode.com/problems/sum-of-square-numbers/

    Enjoy233
  • 牛客网-斐波那契数列

    大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。 n<=39

    TrueDei
  • 杭电oj--1013

    相关数字的根请看我的另一篇博客 一开始,因为题目没有数据大小的要求,我想着只要开个ll就够了,没想过过不去,看来卡的是大数问题,那么就要用字符串进行处理了。 ...

    杨鹏伟
  • Go基础——function函数

    我们以写一个计算商品价格的函数为例,输入参数是单件商品的价格和商品的个数,两者的乘积为商品总价,作为函数的输出值。

    羊羽shine
  • 剑指Offer-变态跳台阶

    package Recursion; /** * 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳...

    武培轩
  • 在Java8的foreach()中使用return/break/continue

    今天使用lambda表达式处理集合时,发现对return、break以及continue的使用有点迷惑,于是自己动手测试了一下,才发现在使用foreach()处...

    Erwin
  • Java工具集-农历日期工具类

    cwl_java

扫码关注云+社区

领取腾讯云代金券