当前位置:网站首页>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
边栏推荐
- Idea one key guide package
- Postman Association
- Nacos - TC Construction of High available seata (02)
- 组播和广播的知识点梳理
- 05. 博客项目之安全
- Driver development - hellowdm driver
- Review of double pointer problems
- Can the feelings of Xi'an version of "Coca Cola" and Bingfeng beverage rush for IPO continue?
- Promotion hung up! The leader said it wasn't my poor skills
- Safe mode on Windows
猜你喜欢
Steady, 35K, byte business data analysis post
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
Idea one key guide package
js Array 列表 实战使用总结
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
【OSPF 和 ISIS 在多路访问网络中对掩码的要求】
Lepton 无损压缩原理及性能分析
浅谈镜头滤镜的类型及作用
[effective Objective-C] - memory management
Class inheritance in yyds dry inventory C
随机推荐
Vulhub vulnerability recurrence 67_ Supervisor
自建DNS服务器,客户端打开网页慢,解决办法
2022 half year summary
Summary of redis basic knowledge points
Steady, 35K, byte business data analysis post
初识CDN
Leetcode dynamic planning day 16
Nacos - TC Construction of High available seata (02)
Postman test report
[mask requirements of OSPF and Isis in multi access network]
Fiddler installed the certificate, or prompted that the certificate is invalid
[QNX Hypervisor 2.2用户手册]6.3.3 使用共享内存(shmem)虚拟设备
Easy to understand I2C protocol
【OSPF 和 ISIS 在多路访问网络中对掩码的要求】
Compilation et connexion de shader dans games202 - webgl (comprendre la direction)
Questions d'examen écrit classiques du pointeur
用StopWatch 统计代码耗时
Postman Association
Tetris
05. 博客项目之安全