http://www.shangxueba.com/jingyan/2927097.html
[原创]LeetCode-Climbing Stairs(爬楼梯)(Java)
Climbing Stairs(爬楼梯)
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?
假设你在爬一个楼梯,该楼梯有n阶,你有两种爬法,每次爬一阶或者两阶。请问你有多少种爬法到达楼梯顶部。
思路1:递归
给定一个数n,有两种途径到达n
一,从n-1处,爬一阶楼梯到达n
二,从n-2处,爬两阶楼梯到达n
符合典型的递归思想。
结束条件,当n=1时,只有一种爬法。当n=2时,有两种爬法2+0,1+1
代码:
public static int climbStairs(int n) {
if(n == 1)
return 1;
if(n == 2)
return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
}
提交结果:
分析:当n=44时,由于递归的层数太多,需要的内存指数级递增。这也是递归的弊端。而且n越大弊端表现的越明显。
思路:爬楼梯就是裴波那契数列
补:裴波那契数列
斐波那契数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
注:此时a1=0,a2=1,an=a(n-1)+a(n-2)(n>=2,n∈N*)
即:裴波那契数列的第n项的值是第n阶楼梯的爬法的种类数
public static int climbStairs(int n) {
int a = 0;
int b = 1;
int sum = 0;
for(int i = 1; i <= n; i++){
sum = a + b;
a = b;
b = sum;
}
return sum;
}
相关推荐
走踏板LeetCode_70--爬楼梯 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 注意:给定 n 将是一个正整数。 示例 1: 输入:2 输出:2 说明:登顶有两种...
leetcode 走踏板爬楼梯 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 注意:给定 n 将是一个正整数。 示例 1: 输入:2 输出:2 解释:有两种方法可以...
走踏板爬楼梯 Leetcode 问题 70 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 示例 1: Input: 2 Output: 2 Explanation: There are two ways to ...
leetcode-java leetcode刷题笔记 已做题目列表 1.Two Sum 3.Longest Substring Without Repeating Characters 5.Longest Palindromic Substring 20.Valid Parentheses 26.Remove Duplicates from Sorted Array 53....
leetcode 走踏板爬楼梯 力码练习 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 注意:给定 n 将是一个正整数。
leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions No. Problem LeetCode 力扣 Python Go Solution Difficulty Tag 0017 Letter Combinations of a Phone Number Medium 回溯、暴力 0034...
Stairs](./leetcode/动态规划-Climbing Stairs.java) [动态规划-Decode Ways](./leetcode/动态规划-Decode Ways.java) [动态规划-Distinct Subsequences](./leetcode/动态规划-Distinct Subsequences.java) [动态...
70.爬楼梯 (Climbing Stairs) 83.删除排序链表中的重复元素 (Remove Duplicates from Sorted List) 88.合并两个有序数组 (Merge Sorted Array) 100.相同的树 (Same Tree) 104.二叉树的最大深度 (Maximum Depth of ...
leetcode 答案 LeetCode-Trip LeetCode刷题代码,大佬勿入。 为一年后的研究生找工作准备 目标是BAT的算法岗哈哈哈哈哈 争取做到每日一更 嗯…… 19.10.22:鸽了这么久,我又回来了……主要在实验室天天没啥事,过于...
================ LeetCode ================动态编程1. Min Cost Climbing Stairs [746]2. Best Time to Buy and Sell Stock [121]3. Climbing Stairs [70]4. Maximum Subarray [53]5. House Robber [198]6. Range ...
70.爬楼梯 Climbing-Stairs 暴力递归,把所有可能的解法递归出来。 public class Sol_one { public int climbStairs(int n) { return climb_Stairs(0, n); } public int climb_Stairs(int i, int n) { if (i > n) { ...
https://leetcode-cn.com/problems/climbing-stairs/ 爬楼梯问题 假设你正在爬楼梯, 需要 n 阶你才能到达楼顶 每次你可以爬 1 或 2 个台阶, 你有多少种不同的方法可以爬到楼顶呢? 设爬 n 个台阶有 f(n) 种可能 假设...
爬楼梯.cpp [TODO] 746. min-cost-climbing-stairs.cpp 第 4 天: [待办事项] leetcode/1143。 最长公共子序列.cpp 第 5 天: [待办事项] leetcode/221。 最大平方.cpp 利特代码/85。 最大矩形.cpp 第 6 天: ...
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
题目 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?...链接:https://leetcode-cn.com/problems/climbing-stairs 思路 对于这样一个问题
leetcode 答案LeetCode LeetCode in Swift 这个Repo 用来存下我在LeetCode 解题的原始档,包含解题中遇到的错误,也包含解出AC 的答案, 以下的清单将连结到我的Github Pages 中,皆有题目中文翻译与解题的过程。...
Leetcode扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...
Stairs).md](Java基础/数据结构与算法/LeetCode/LeetCode 70. 爬楼梯(Climbing Stairs).md) 7月3号 java 异常详解 7月2号 整理基础算法 7月1号 七月 6月30号 6月29号 6月25号 6月22号 Redis中String、List、Hash...
leetcode卡 leetcode exercises 3-5 solutions everyday. fighting~ TODO array Best Time to Buy and Sell Stock II Valid Sudoku linked list Palindrome linked list Linked List Cycle trees Convert Sorted ...
第 482 章编码测试 JewelsAndStones_771 [Java] Java HashMap、ArrayList 包含方法性能对比 LicenseKeyFormatting_482 [Java] String、StringBuffer、StringBuilder ...[Java] ...ClimbingStairs_70 Q