当前位置:网站首页>Algorithm -- climbing stairs (kotlin)
Algorithm -- climbing stairs (kotlin)
2022-07-06 05:22:00 【Xiaomi technology Android research and development caoxinyu】
subject
Suppose you're climbing the stairs . need n You can reach the top of the building .
Every time you climb 1 or 2 A stair . How many different ways can you climb to the top of the building ?
Example 1:
Input :n = 2
Output :2
explain : There are two ways to climb to the top .
1. 1 rank + 1 rank
2. 2 rank
Example 2:
Input :n = 3
Output :3
explain : There are three ways to climb to the top .
1 rank + 1 rank + 1 rank
1 rank + 2 rank
2 rank + 1 rank
Tips :
1 <= n <= 45
https://leetcode.cn/problems/climbing-stairs/
Solutions
- In fact, the conventional solution of this problem can be divided into several subproblems , Climb the first n The number of ways to step stairs , be equal to 2 The sum of parts
Climb up n-1 The number of ways to step stairs . Because climb again 1 You can get to the third level n rank
Climb up n-2 The number of ways to step stairs , Because climb again 2 You can get to the third level n rank
So we get the formula dp[n] = dp[n-1] + dp[n-2]
At the same time, you need to initialize dp[0]=1 and dp[1]=1d
Time complexity :O(n)
2. since dp[n] = dp[n-1] + dp[n-2]
Then we can use sliding array to solve it
resolvent
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
}
summary
1. I didn't figure out how to do this problem
I read the solution of the problem before I worked it out
边栏推荐
- Collection + interview questions
- Summary of redis basic knowledge points
- Fuzzy -- basic application method of AFL
- Select knowledge points of structure
- 02. 开发博客项目之数据存储
- Vulhub vulnerability recurrence 71_ Unomi
- F12 solve the problem that web pages cannot be copied
- 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
- TCP three handshakes you need to know
- JDBC calls the stored procedure with call and reports an error
猜你喜欢
ByteDance program yuan teaches you how to brush algorithm questions: I'm not afraid of the interviewer tearing the code
05. 博客项目之安全
Can the feelings of Xi'an version of "Coca Cola" and Bingfeng beverage rush for IPO continue?
Codeforces Round #804 (Div. 2) Editorial(A-B)
Graduation design game mall
Golang -- TCP implements concurrency (server and client)
Pagoda configuration mongodb
Postman Association
Ora-01779: the column corresponding to the non key value saving table cannot be modified
Principle and performance analysis of lepton lossless compression
随机推荐
Oracle query table index, unique constraint, field
HAC cluster modifying administrator user password
Principle and performance analysis of lepton lossless compression
Using stopwatch to count code time
Compilation et connexion de shader dans games202 - webgl (comprendre la direction)
Postman manage test cases
集合详解之 Map + 面试题
04. Project blog log
[mask requirements of OSPF and Isis in multi access network]
【torch】|torch.nn.utils.clip_grad_norm_
Hyperledger Fabric2. Some basic concepts of X (1)
Excel转换为Lua的配置文件
[noip2009 popularization group] score line delimitation
Hometown 20 years later (primary school exercises)
JS quick start (II)
Questions d'examen écrit classiques du pointeur
趋势前沿 | 达摩院语音 AI 最新技术大全
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
nacos-高可用seata之TC搭建(02)
Simple understanding of interpreters and compilers