当前位置:网站首页>算法-- 爬楼梯(Kotlin)
算法-- 爬楼梯(Kotlin)
2022-07-06 05:18:00 【小米科技Android 研发曹新雨】
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
示例 1:
输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2:
输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶
提示:
1 <= n <= 45
https://leetcode.cn/problems/climbing-stairs/
解决思路
- 本问题其实常规解法可以分成多个子问题,爬第n阶楼梯的方法数量,等于 2 部分之和
爬上 n-1阶楼梯的方法数量。因为再爬1阶就能到第n阶
爬上 n-2阶楼梯的方法数量,因为再爬2阶就能到第n阶
所以我们得到公式 dp[n] = dp[n-1] + dp[n-2]
同时需要初始化 dp[0]=1 和 dp[1]=1d
时间复杂度:O(n)
2.既然 dp[n] = dp[n-1] + dp[n-2]
那么我们可以用滑动数组去解决
解决方法
fun climbStairs(n: Int): Int {
val intArray = IntArray(n + 1)
intArray[0] = 1
intArray[1] = 1
for (i in 2..n) {
intArray[i] = intArray[i - 1] + intArray[i - 2]
}
return intArray[n]
}
fun climbStairs2(n: Int): Int {
var q = 1
var p = 1
var result = 1
for (i in 2..n) {
result = q + p
q = p
p = result
}
return result
}
总结
1.这个题一下没有想出来怎么做
看了一下题解才做出来
边栏推荐
- 指针经典笔试题
- C# AES对字符串进行加密
- 关于Unity Inspector上的一些常用技巧,一般用于编辑器扩展或者其他
- Tetris
- Realize a binary read-write address book
- Application of Flody
- [leetcode16] the sum of the nearest three numbers (double pointer)
- The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
- Steady, 35K, byte business data analysis post
- Fiddler installed the certificate, or prompted that the certificate is invalid
猜你喜欢
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
[leetcode16] the sum of the nearest three numbers (double pointer)
Extension of graph theory
Pagoda configuration mongodb
Vite configures the development environment and production environment
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
指针经典笔试题
RT thread analysis - object container implementation and function
First acquaintance with CDN
Hyperledger Fabric2. Some basic concepts of X (1)
随机推荐
Knowledge points of circular structure
04. 项目博客之日志
[buuctf.reverse] 159_[watevrCTF 2019]Watshell
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Modbus protocol communication exception
pix2pix:使用条件对抗网络的图像到图像转换
Implementing fuzzy query with dataframe
Codeforces Round #804 (Div. 2)
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
First acquaintance with CDN
Codeforces Round #804 (Div. 2) Editorial(A-B)
Drive development - the first helloddk
RT thread analysis - object container implementation and function
JS quick start (II)
趋势前沿 | 达摩院语音 AI 最新技术大全
[noip2008 improvement group] stupid monkey
A little knowledge of CPU, disk and memory
【torch】|torch. nn. utils. clip_ grad_ norm_
Postman manage test cases
Vulhub vulnerability recurrence 67_ Supervisor