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 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-867-Transpose Matrix(矩阵由按行存储变成按列存储)

Given a matrix A, return the transpose of A.

1502
来自专栏Leetcode名企之路

【Leetcode】81. 搜索旋转排序数组 II

( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

2022
来自专栏用户画像

Python语言实现Dijkstra算法

Dijkstra算法是由荷兰计算机科学家狄克斯特拉(Dijkstra)于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决...

1773
来自专栏编程理解

数据结构(十):最小生成树

,向生成树中添加任意一条边,则会形成环。生成树存在多种,其中权值之和最小的生成树即为最小生成树。

1043
来自专栏Leetcode名企之路

【Leetcode】59. 螺旋矩阵 II

给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

1413
来自专栏C#

DotNet生成随机数的一些方法

  在项目开发中,一般都会使用到“随机数”,但是在DotNet中的随机数并非真正的随机数,可在一些情况下生成重复的数字,现在总结一下在项目中生成随机数的...

2017
来自专栏数据结构与算法

洛谷P2084 进制转换

题目背景 无 题目描述 今天小明学会了进制转换,比如(10101)2 ,那么它的十进制表示的式子就是 : 那么请你编程实现,将一个M进制的数N转换成十...

2583
来自专栏云霄雨霁

无向图----深度优先搜索

2740
来自专栏tkokof 的技术,小趣及杂念

OpenGL ES Shading Language 2.0 参考笔记

声明 struct matStruct { vec4 ambientColor; vec4 diffuseColor; ...

951
来自专栏机器学习从入门到成神

2013百度校招笔试真题以及解析(二)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1021

扫码关注云+社区

领取腾讯云代金券