首页 > 试题广场 >

最小花费爬楼梯

[编程题]最小花费爬楼梯

热度指数：59216 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整数数组 $cost \$ ，其中 $cost[i]\$ 是从楼梯第 $i \$ 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

数据范围：数组长度满足 $1 \le n \le 10^5 \$ ，数组中的值满足 $1 \le cost_i \le 10^4 \$

示例1

输入

[2,5,20]

输出

说明

你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5

示例2

输入

[1,100,1,1,1,90,1,1,80,1]

输出

说明

你将从下标为 0 的台阶开始。
1.支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
2.支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
3.支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
4.支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
5.支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
6.支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

算法知识视频讲解

一个优雅的程序猿

#define min(a,b)   (a>b ? b : a)
int minCostClimbingStairs(int* cost, int costLen ) {
    int res[100001], i;
    res[0] = 0;
    res[1] = 0;
    for(i=2; i<=costLen; i++)
    res[i] = min(res[i-1]+cost[i-1], res[i-2]+cost[i-2]);
    return res[costLen];
}

编辑于 2024-03-23 22:53:44 回复(0)

周香华

#include <math.h>

int minCostClimbingStairs(int* cost, int costLen ) {

// write code here

int dp[costLen];

dp[0]=0;dp[1]=0;

for(int i=2;i<=costLen;i++)

{

dp[2]=fmin(dp[0]+cost[i-2],dp[1]+cost[i-1]);

dp[0]=dp[1];

dp[1]=dp[2];

}

return dp[2];

}

发表于 2023-10-14 20:12:07 回复(0)

飞天马里奥

int minCostClimbingStairs(int* cost, int costLen ) {
    // write code here
    // int ret = 0;

    int dp[costLen];

    dp[0] = 0;
    dp[1] = 0;

    for(int i = 2; i <= costLen; i++){
        dp[i] = (dp[i - 1] + cost[i - 1]) > (dp[i - 2] + cost[i - 2]) ? (dp[i - 2] + cost[i - 2]) : (dp[i - 1] + cost[i - 1]);
        
    }
    return dp[costLen];
}

发表于 2023-02-23 17:13:36 回复(1)

JayneChou

#include <math.h>
#include <stdlib.h>
int minCostClimbingStairs(int* cost, int costLen ) {
    int *minCost = (int*)malloc(sizeof(int) * (costLen + 1));
    minCost[0] = 0, minCost[1] = 0;//在clion里默认初始化为0，这里没有害我浪费半个小时
    for(int i = 2; i <= costLen; i++){
        minCost[i] = (int)fmin(cost[i - 1] + minCost[i - 1], cost[i - 2] + minCost[i - 2]);
    }
    return minCost[costLen];
}

发表于 2023-02-18 16:34:31 回复(0)

cloudyshun

int minCostClimbingStairs(int* cost, int costLen ) {

// write code here

if (costLen == 1){

return 0;

}

int fei[costLen + 1];

fei[0] = fei[1] = 0;

for(int i = 2; i < costLen + 1; i++){

if((fei[i-2] + cost[i-2]) < (fei[i-1] + cost[i-1])){

fei[i] = (fei[i-2] + cost[i-2]);

}else{

fei[i] = (fei[i-1] + cost[i-1]);

}

return fei[costLen];

}

发表于 2023-01-01 14:13:25 回复(0)

牛客42558553号

int minCostClimbingStairs(int* cost, int costLen ) {
    // write code here
    if(costLen==1||costLen ==0)
    {
        return 0;
    }
    int count1 = minCostClimbingStairs(cost,costLen-1) + cost[costLen-1];
    int count2 = minCostClimbingStairs(cost,costLen-2) + cost[costLen-2];
    return count1<count2?count1:count2;
}

一开始用C++写发现时间超了，以为这道题只能用C写，用C写发现时间也超了，官方就完全不给活路呗。

发表于 2022-12-27 17:52:34 回复(0)

牛客579577851号

//从第n-1或n-2层开始往前推

//n-1 或 n-2至终点的最小花费是已知的

int Method3(int cost[],int start , const int end){ //动态规划

int cost1 = cost[end - 2];

int cost2 = cost[end - 1];

int t;

//cost1 始终在cost2之前

for(int round = end - 3;round >= 0;round--){

t = cost1;

cost1 = cost[round] + ((cost1 > cost2)?cost2 : cost1);

cost2 = t;

}

return cost1<cost2?cost1:cost2;//选较小值

}

int minCostClimbingStairs(int* cost, int costLen ) {

// write code here

return Method3(cost, 0, costLen);

}

发表于 2022-12-13 13:02:58 回复(0)

夕木月

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param cost int整型一维数组
* @param costLen int cost数组长度
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
//这个递归会超时
int recost(int* cost, int rellycostLen )
{
if(rellycostLen == 2)
return 0;
//return cost[0];
if(rellycostLen == 3)
return (cost[0] < cost[1]) ? cost[0] : cost[1];

int a = 0;
int b = 0;
int c = 0;
for(int i = 3;i <= rellycostLen;i++)//这种就不会超时
{
c = a+cost[i-3] < b+cost[i-2] ? a+cost[i-3] : b+cost[i-2] ;
a = b;
b = c;

}
return c;

//下面这个递归会超时
//return (recost(cost,rellycostLen-1)+cost[rellycostLen-2] < recost(cost,rellycostLen-2)+cost[rellycostLen-3] ) ?
// recost(cost,rellycostLen-1)+cost[rellycostLen-2] : recost(cost,rellycostLen-2)+cost[rellycostLen-3];
}

int minCostClimbingStairs(int* cost, int costLen )
{
// write code here
if(costLen == 1)
return 0;
if(costLen == 2)
return (cost[0] < cost[1]) ? cost[0] : cost[1];

return recost(cost,costLen+1);
}

发表于 2022-07-28 16:19:02 回复(1)

taishan

这一题运用动态规划的基本思想就是

我们上第一和第二阶台阶的最小费用都为0，可以直接从地面跳上去；

我们上第三阶台阶的最小费用，取决于上第一和第第二阶台阶的最小费用；

同理，我们上第n阶的最小费用，就取决于上第n-1阶台阶费用+cost【n-1】和上第n-2阶台阶的费用+cost[n-2]；

值得注意的是我们要上的是楼顶，楼梯总共有n阶，所以我们要求上n+1阶台阶的最小费用。

int minCostClimbingStairs(int* cost, int costLen ) {

// write code here
if(costLen>2)
{
int min=0;
int min1=0;
int min2=0;
int a[costLen];
int i;
for(i=2;i<=costLen;i++)
{
if((min1+cost[i-2])<(min2+cost[i-1]))
min=min1+cost[i-2];
else
min=min2+cost[i-1];
min1=min2;
min2=min;
}
return min;
}
else
return 0;
}

发表于 2022-07-14 21:13:17 回复(0)