原题链接:#7 Climbing Stairs
问题:
你正在攀爬一把一共有n个台阶的梯子,每次可以爬一或二阶,爬到顶共有多少种不同的方式?
难度:简单
分析:
当梯子阶数为0时,有0种攀爬方式;当阶数为1时,则有一种攀爬方式。当阶数为2时,由于每次可以爬一阶或两阶,即从0阶处爬两阶到达顶部或由1阶处爬1阶到达顶处,共2种方式。n=3时同样,可以由1阶处爬两阶或由2阶处爬1阶到达。设对于i阶阶梯不同的攀爬方式为S(i),可得递推公式为 S(i) = S(i-1) + S(i-2) (2≤i≤n) (看起来很眼熟 ;-))
解决方案:
Java - 244ms
public int climbStairs(int n) { if(n==0||n==1||n==2){ return n; } int[] ways = new int[n+1]; ways[0] = 0; ways[1] = 1; ways[2] = 2; for(int i=3; i<=n; i++){ ways[i] = ways[i-1] + ways[i-2]; } return ways[n]; }
相关推荐
leetcode 走踏板LeetCode_70--爬楼梯 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 注意:给定 n 将是一个正整数。 示例 1: 输入:2 输出:2 说明:...
leetcode 走踏板爬楼梯 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 注意:给定 n 将是一个正整数。 示例 1: 输入:2 输出:2 解释:有两种方法可以...
leetcode 走踏板爬楼梯 Leetcode 问题 70 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 示例 1: Input: 2 Output: 2 Explanation: There are two ...
Stairs](./leetcode/动态规划-Climbing Stairs.java) [动态规划-Decode Ways](./leetcode/动态规划-Decode Ways.java) [动态规划-Distinct Subsequences](./leetcode/动态规划-Distinct Subsequences.java) [动态...
leetcode 走踏板爬楼梯 力码练习 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 注意:给定 n 将是一个正整数。
leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions No. Problem ...动态规划 0069 Sqrt(x) Easy 二分、牛顿迭代 0070 Climbing Stairs Easy 动态规划 0075 Sort Colors M
================ 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 ...
动态规划 参考: 第一天: [待办事项] 509.fibonacci-number.cpp [待办事项] 322.coin-change.cpp 第 2 天: [待办事项] 62.unique-paths.cpp [TODO] 5. 最长回文子串.cpp 第 3 天: [TODO] 96.unique-binary-search...
leetcode 答案LeetCode LeetCode in Swift 这个Repo 用来存下我在LeetCode 解题的原始档,包含解题中遇到的错误,也包含解出AC 的答案, 以下的清单将连结到我的Github Pages 中,皆有题目中文翻译与解题的过程。...
leetcode 答案 LeetCode-Trip LeetCode刷题代码,大佬勿入。 为一年后的研究生找工作准备 目标是BAT的算法岗哈哈哈哈哈 争取做到每日一更 嗯…… 19.10.22:鸽了这么久,我又回来了……主要在实验室天天没啥事,过于...
53.最大子数组(python:动态规划)** 58.Last Word (c++) 66.Plus One (c++) 67.添加二进制(C++) 69.Sqrt(x) (c++:二元除法) 70.Climbing Stairs(c++:Dynamic Programming) 83.从排序列表中删除重复项(c++) 88....
动态规划,类似于求最大连续和,但这里由于是乘法,还要考虑符号问题。于是需要记录最大与最小值。 Reverse Words in a String C++实现时那个返回值是void也着实让我困惑了好久 Subsets DFS实现,竟然还WA了好几次。...
leetcode卡 leetcode exercises 3-5 solutions everyday. fighting~ TODO array Best ...动态规划:背包问题、最长子序列 数据结构,主要有如下几种: 数组与链表:单 / 双向链表 栈与队列 哈希表 堆:
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...
第 482 章编码测试 JewelsAndStones_771 [Java] Java HashMap、ArrayList 包含方法性能对比 LicenseKeyFormatting_482 [Java] String、StringBuffer、StringBuilder 的区别和优缺点 ...ClimbingStairs_70 Q
70.Climbing Stairs 121.Best Time to Buy and Sell Stock 122.Best Time to Buy and Sell Stock II 123.Best Time to Buy and Sell Stock III 141.Linked List Cycle 142.Linked List Cycle II 188.Best Time to ...
Leetcode经典01背包UVA Problem This repository include my answer about the UVA exam problem at the same time include some comment and what my thinking about problem 同时还会放入一些经典的问题的解答思考...
看了下Dscuss,搜索了一下,发现这道居然就是典型的动态规划题,用哈希把子问题的答案记录了就能节省大量的运行时间。 Linked List Cycle 判断链表是否有环。通过快慢节点可以简单实现。 Unique Binary Search Trees...
leetcode小岛出水口 leetcode training one problem on file 为了方便文档管理,项目逐渐文档化,以单个文件作为集合最小集。 go语言不能完全适合写算法题 后续会尽可能加入rust或者c的题解 清单 0965. Univalued ...