当前位置:网站首页>746. Climb stairs with minimum cost
746. Climb stairs with minimum cost
2022-07-04 06:01:00 【mrbone9】
Address :
Power button https://leetcode-cn.com/problems/min-cost-climbing-stairs/
subject :
Give you an array of integers cost , among cost[i] It's from the stairs i The cost of climbing a step up . Once you pay this fee , You can choose to climb up one or two steps .
You can choose from the subscript to 0 Or subscript 1 The steps began to climb the stairs .
Please calculate and return the minimum cost to reach the top of the stairs .
Example 1:
Input :cost = [10,15,20] Output :15 explain : You will subscript 1 The steps begin . - payment 15 , Climb up two steps , Get to the top of the stairs . The total cost is 15 . |
Example 2:
Input :cost = [1,100,1,1,1,100,1,1,100,1] Output :6 explain : You will subscript 0 The steps begin . - payment 1 , Climb up two steps , The arrival subscript is 2 The steps of . - payment 1 , Climb up two steps , The arrival subscript is 4 The steps of . - payment 1 , Climb up two steps , The arrival subscript is 6 The steps of . - payment 1 , Climb up a step , The arrival subscript is 7 The steps of . - payment 1 , Climb up two steps , The arrival subscript is 9 The steps of . - payment 1 , Climb up a step , Get to the top of the stairs . The total cost is 6 . |
Tips :
2 <= cost.length <= 1000 0 <= cost[i] <= 999 |
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/min-cost-climbing-stairs
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas :
This is (LeetCode-70) climb stairs A derivative version of , We use the idea of dynamic programming to deal with
1. The first i The cost of a step is dp[i]
2. The first i The next step is from i-1 perhaps i-2 Up the steps , That is to say
dp[i-1] Add the cost of this step up perhaps
dp[i-2] Add the cost of this step up
3. Then the formula can be set as :
dp[i] = min(dp[i-1] + cost[i-1] , dp[i-2] + cost[i-2]);
4. Initial element settings
dp[0] = 0; dp[1] = 0;
These two are the initial stages , It hasn't started to go up yet , So there is no cost
The topic gives a range of expenses :2 <= cost.length <= 1000
that dp[10001] That's all right.
Method 1 、 Dynamic programming
#define min(a,b) ( (a) < (b) ? (a) : (b) )
int minCostClimbingStairs(int* cost, int costSize){
int i;
int dp[1001]={0,0};
for(i=2; i<=costSize; i++)
{
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
}
return dp[costSize];
}
边栏推荐
- Use of hutool Pinyin tool
- How to configure static IP for Kali virtual machine
- BUU-Crypto-[HDCTF2019]basic rsa
- 体验碎周报第 102 期(2022.7.4)
- Component、Container容器常用API详解:Frame、Panel、ScrollPane
- 每周小结(*63):关于正能量
- Upper computer software development - log information is stored in the database based on log4net
- C语言练习题(递归)
- JSON Web Token----JWT和傳統session登錄認證對比
- Kubernets first meeting
猜你喜欢
Zhanrui tankbang | jointly build, cooperate and win-win zhanrui core ecology
BUU-Crypto-[GUET-CTF2019]BabyRSA
ES6 模块化
卸载Google Drive 硬盘-必须退出程序才能卸载
[excel] PivotChart
How does apscheduler set tasks not to be concurrent (that is, execute the next task after the first one)?
Design and implementation of redis 7.0 multi part AOF
C # character similarity comparison general class
How to avoid JVM memory leakage?
体验碎周报第 102 期(2022.7.4)
随机推荐
left_ and_ right_ Net interpretable design
tutle时钟改进版
Excel comparator
How to clone objects
Understanding of cross domain and how to solve cross domain problems
Penetration tool - sqlmap
Leetcode question brushing record | 206_ Reverse linked list
Gridview出现滚动条,组件冲突,如何解决
Arc135 a (time complexity analysis)
Invalid revision: 3.18.1-g262b901-dirty
安装 Pytorch geometric
Configure cross compilation tool chain and environment variables
【微服务】Nacos集群搭建以及加载文件配置
ANSYS command
BUU-Crypto-Cipher
BUU-Crypto-[HDCTF2019]basic rsa
Google Chrome browser will support the function of selecting text translation
JS get the attribute values nested in the object
如何实现视频平台会员多账号登录
JS flattened array of number shape structure